ひとりで勝手にはじめた蟻本読書会 セグメント木 遅延評価セグメント木で区間の総和・最大値（最小値）を素早く計算する の続きです。
フェニック木とセグメント木の違い
Binary Indexed Tree（BIT 別名 フェニック木）は区間の和に対するクエリ（Range Sum Query）を効率的に処理するデータ構造です。区間の和は初項からという制約がありますが、任意区間（a, b）であっても sum(b) – sum(a – 1) で計算可能なので任意区間の総和を求めるときにも使うことができます。
区間和は初項からしか計算しないという条件が加わるとセグメント木はどうなるでしょうか？
セグメントでは配列 A の和は以下のように格納されていました。
A[0] から A[x] の和は以下のノードを使えば計算できます。
ここで使われていない部分があることに気が付きます。
使われていないのであれば省略できます。そのぶんメモリーを節約することができるのです。
配列の添字は以下のようにします。0 は使いません。区間の右端で番号づけをするのです。使用する配列の長さは管理したい配列の長さに 1 を足したものです。セグメント木とちがって 2 の N 乗にする必要はありません。
更新は下から順番におこないますが、つぎに更新処理をする区間は番号に区間の長さを足すことで求められます。そしてbit[x] が管理する区間の長さは，x の最も下の立っているビット x & -x で求めることができます。
bit[1] を更新したら 1 + (1 & -1) = 2 となり、bit[2] を更新したら 2 + (2 & -2) = 4、bit[4] を更新したら 4 + (4 & -4) = 8 となるのです。添字と bit のサイズ -1 が同じになったのでここで終了です。
Bitクラスを定義する
以下は配列のサイズを指定したら添字を指定して値を増加させる、添字を指定して[0, index]までの総和を求めるクラスを定義したものです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
using System; using System.Collections.Generic; using System.Linq; class Bit { int Size = 0; long[] A = { }; public Bit(int n) { Size = n; A = new long[n + 1]; } public void Add(int i, long value) { i++; while (i <= Size) { A[i] += value; i += i & -i; } } public long GetSum(int i) { i++; long sum = 0; while (i > 0) { sum += A[i]; i -= i & -i; } return sum; } } |
B – Fenwick Tree
これで以下を解いてみることにします。
長さ N の数列 a[0], a[1], …, a[N-1] に Q 個のクエリが飛んできます。処理してください。
0 p x ⇒ a[p] の値を x 増加させる
1 l r ⇒ a[l] から a[r-1] までの総和を出力する入力されるデータ
N Q
a[0] a[1] … a[N-1]
Query 0
Query 1
Query Q-1（ただし、1 ≦ N, Q ≦ 500,000
0 ≦ a[i], x ≦ 10^9 ）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// Bitクラスの定義は同じなので省略 class Program { static void Main() { int N, Q; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; Q = vs[1]; } int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Bit bit = new Bit(N); for (int i = 0; i < A.Length; i++) bit.Add(i, A[i]); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); if (vs[0] == 0) { int p = vs[1]; long x = vs[2]; bit.Add(vs[1], p, x); } if (vs[0] == 1) { int l = vs[1]; int r = vs[2]; // 半開区間 [l, r) の総和を計算する // S[r - 1] - S[l - 1] を計算する（初項からの総和なら - S[l - 1] は不要） long sum = bit.GetSum(r - 1); if(l > 0) sum -= bit.GetSum(l - 1); Console.WriteLine(sum); } } } } |
C – データ構造
数の集合 S に対する以下のクエリを処理してください。
タイプ 1 ： S に数 X を追加する。
タイプ 2 ： S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する。入力されるデータ
Q
T_1 X_1
T_2 X_2
:
T_Q X_Qただし、
Q はクエリの個数 Q(1 ≦ Q ≦ 200,000)
T_i はクエリのタイプ 1 または 2
1 ≦ X_i ≦ 200,000
「X 番目の数」とは「それ以下の数が X 個であるような数のうち最小のもの」です。そのため「ある数 X 以下の数がいくつあるか」を高速に求めることができるデータ構造があればあとは二分探索で求めることができそうです。
配列 A を定義し、S に数 X を追加する動作を A[X] をインクリメントすることにします。すると A[0] ～ A[X] の総和は X 以下の数の個数となります。フェニック木を使えばうまくいきそうです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
using System; using System.Collections.Generic; using System.Linq; // Bitクラスの定義は同じなので省略 class Program { static void Main() { // X の 最大値が 200,000 なのでフェニック木で管理する配列はそれより 1 大きい配列とする int arrayLength = 200001; Bit bit = new Bit(arrayLength); int Q = int.Parse(Console.ReadLine()); List<int> rets = new List<int>(); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = vs[0]; int x = vs[1]; if(t == 1) { bit.Add(x, 1); } if (t == 2) { int left = 0; int right = arrayLength; // 「x 番目の数」＝「それ以下の数が x 個であるような数のうち最小のもの」を // 二分探索法で探す（x <= bit.GetSum(mid) となる最小のものを探せばよい） while (true) { int mid = (left + right) / 2; if (x <= bit.GetSum(mid)) right = mid; else left = mid; if (right - left <= 1) { rets.Add(right); bit.Add(right, -1); // 見つけたら取り除く（個数を -1 すればよい） break; } } } } foreach(int ret in rets) Console.WriteLine(ret); } } |
区間全体に対して値を加算する処理
上記の方法だと特定の要素にしか値を加算することができません。区間全体に対して値を加算するためにはどうすればよいでしょうか？
差分に着目します。BITオブジェクトを 2 個使うことでできるようになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
using System; using System.Collections.Generic; using System.Linq; // Bitクラスの定義は同じなので省略 class RangeAddBit { Bit p = null; Bit q = null; public RangeAddBit(int n) { p = new Bit(n + 1); q = new Bit(n + 1); } public void Add(int s, int t, long value) { t += 1; p.Add(s, -value * s); p.Add(t, value * t); q.Add(s, value); q.Add(t, -value); } public long GetSum(int s, int t) { t += 1; return p.GetSum(t) + q.GetSum(t) * t - p.GetSum(s) - q.GetSum(s) * s; } } class Program { static void Main() { int N, Q; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; Q = vs[1]; } int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); RangeAddBit bit = new RangeAddBit(N); for (int i = 0; i < A.Length; i++) bit.Add(i, i, A[i]); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); if (vs[0] == 0) { bit.Add(vs[1], vs[1], vs[2]); } if (vs[0] == 1) { int l = vs[1]; int r = vs[2]; long sum = bit.GetSum(l, r - 1); // 半開区間 [l, r) を 閉区間 [l, r - 1] に Console.WriteLine(sum); } } } } |
