練習のための問題は 競技プログラミングの履歴、LSB(least significant bit)については二進展開(MSB/LSB)で
フェニック木(Binary Indexed Tree)
フェニック木は1993年にピーター・フェニックにより提案された木構造です。
フェニック木を使えば、今まで累積和を使って計算したような区間の和がある程度少ない実装で高速に実行できるようです。
この構造のキモは「区間の和を求める際にすべての区間の値をそのまま持たないほうが早く計算できね?」→「和を木構造に配置して取り出すときは親をたどって足し算するようにしたわ」みたいな感じ
フェニック木で使う操作は以下の通り、正直プログラミング的には元の名称はイマイチですね…
名称 | 機能 | フェニックの論文での名称 | 備考 |
---|---|---|---|
n/a | ある区間の元の差分を求める | GetCuml | 元データが欲しい場合(実際のソフトウェアなど)には必要だが、競プロではたぶん不要。なぜなら元データが所与として与えられるし… |
add | ある値を木に追加する(O(log n)) | PutValue | 木構造に値を追加する。早い。 |
sum | 区間0~Nまでの和を返す(O(log n)) | GetProb | ここがこの木構造で一番やりたいこと。区間和を高速にとれる。 |
range | 区間L~Rまでの和を返す(O(log n)) | n/a | 上を拡張して、指定したインデックス間の区間和がとれる。 |
lower_bound | 区間0〜Nまでの範囲において、ある値Wよりも大きい区間和の最初のインデックスを返す(O(log n)) | getIndex | 微妙に説明が少ない |
max | 区間L~Rまでの最大値を返す(O(n)) | n/a | |
min | 区間L~Rまでの最小値を返す(O(log n)) | n/a | フェニックの論文にはない、2方向から二分探索する |
詳しい解説
- Binary Indexed Tree もしくはフェニック木について
- 有志のスライド
- Binary indexed tree
- こっちのほうがわかりやすい、区間の和まではこれで理解できる
- Binary indexed tree
- Binary Indexed Tree のはなし - hos.ac
- 頭いい人向け、フェニック木上での二分探索までわかる
- LSB(least significant bit)
- 原文
- Peter M. Fenwick. A new data structure for cumulative frequency tables. Software - Practice and Experience, 24(3):327--336, March 1994.
フェニック木(区間の和)
解説(GeeksForGeeks)
Binary Indexed Tree もしくはフェニック木について
Binary Indexed Treeを理解するために次の問題について考えてみましょう。
ある配列 arr[0...n-1] があるとしましょう、これを以下のように操作する必要があります
- 最初のi番目までの和を求める
- 0 <= i <= n-1の範囲で、arr[i] = x のように指定された要素を更新する
これについての単純な解法は、0からi-1まで巡回して要素の和を計算することです。値を更新するためには、arr[i] = xを実行すればよいです。最初の操作はO(n)の時間がかかり、そして次の操作はO(1)の時間がかかります。(訳者注:素朴な全探索)
次の単純な解法は、もう一つの配列を作成し最初からi番目までの和をその配列の同じインデックスに保存しておくというものです。与えられた範囲の和はこれでO(1)の時間で計算できますが、更新の操作にはO(n)時間がかかってしまいます。これは実行するクエリが膨大で、更新が少ない場合に有効です。(訳者注:累積和)
この両方の操作に対してO(log n)時間で処理を行うことは可能でしょうか?有効な解決策はセグメント木を使うことです。これはどちらの操作もO(log n)時間で行うことができます。
Binary Indexed Tree(以下、フェニック木)を使うことで、両方の操作に対してO(log n)時間で処理を行うことができます。セグメント木よりもフェニック木が有用な点は、実装が容易でメモリ空間をとらないことです。。。
- 説明
- フェニック木は1つの配列で表現されます。配列名を@bit[]としましょう。フェニック木のそれぞれのノードは与えられた配列のいくつかの要素の和を保存します。フェニック木のサイズは入力値の配列とおなじです。以下のコードでは、実装の簡単化のためにサイズはn+1としている。
- 構造
- フェニック木の初期化の際、@bit[]はすべて0で埋めます。次に更新操作を呼び、すべてのインデックスに実際の和を入れていきます。更新の操作の方法については、下のほうで議論します。
- 操作
sum
sum(index): arr[0..index]の和を返す arr[0..index]の和を返す時には@bit[0..n]を使用する。 これは、@bit[]が与えられた配列arr[0..n-1]で構築されていることを前提としている。 (1) 和を0で初期化し、インデックスはインクリメントする (2) インデックスが0以上である限り以下を繰り返す ...(a) @bit[index]の値を返却するsumに加える ...(b) @bit[index]の親を辿る。親のノードはインデックス値からLSB(last set bit)を除くことで手に入る。 i.e. index = index - (index & (-index)) (ex) index = 7(=00000111), LSB(7)=1 なので 00000111から1番目のbitを削除 index = 6(=00000110), LSB(6)=2 なので 00000110から2番目のbitを削除 index = 4(=00000100), LSB(4)=3 なので 00000100から3番目のbitを削除 index = 0(=00000000), 0は最上の親要素なのでループ終了
以下の図はgetSum()がどのように動作するか示したものです。以下のような重要な観察が得られます。
- インデックス=0のノードはダミー
- インデックスyのノードはインデックスxのノードの親
- yはxの2進数表現からLSBを削除してやると取得できる
- xのノードの子yは、yを除いたxの要素の和を保持する
add
add(index, val): '''arr[index] += val'''という操作によりフェニック木を更新する 配列arr[]はここでは変更されない、この操作は@bit[]を変更するのみである。 (1) インデックスをインクリメントする (2) インデックスがN以下である限り以下を繰り返す ...(a) @bit[index]に値を加算 ...(b) @bit[index]の親に遷移。親のノードはインデックス値からLSB(last set bit)を除くことで手に入る。
練習問題
AOJ DSL_2_B
- Range Query - Range Sum Query (RSQ) - Aizu Online Judge
- 回答のコード #2942008 Solution for DSL_2_B by hiroyuking
- 0-indexedかそうでないかでハマった
よくわからない自分のための注釈
- とりあえずソースコードは以下
+ | fenwick_tree.rb |
- 具体例として以下のような木を作ってみる
- コードだと以下のような感じ
a = [5,3,7,9,6,4,1,2] ft = FenwickTree.new(a.length, a) p ft.bit # [0, 5, 8, 7, 24, 6, 10, 1, 37]
- sumの結果、区間0~nまでの和が正しく計算できた
n | sum(n) |
---|---|
0 | 5 |
1 | 8 |
2 | 15 |
3 | 24 |
4 | 30 |
5 | 34 |
6 | 35 |
7 | 37 |
フェニック木(ある値Wよりも大きい区間和)
解説(Fenwickの論文から)
- 操作
- GeeksForGeeksには解説がないので、いろいろ調べて日本語化
lower_bound
lower_bound(w): 区間0〜Nまでの範囲において、ある値Wよりも大きい区間和の最初のインデックスを返す すでに構築済みの変数に加えて、@n2を使用する。 これは、フェニック木の構築時に作成する配列の要素数Nよりも小さい最大の2のべき乗 例えば配列の要素数が16であれば8がその数になる。 (1) インデックスを0で初期化、マスクを@n2で初期化 (2) マスクが0でない限り以下を繰り返す ...(a) インデックス値とマスクの和をテストインデックス(tidx)として定義 ...(b) もし@bit[tidx]よりWの値が大きければ ・インデックスをテストインデックスの値で上書き ・Wから@bit[tidx]の値を引く ...(c) マスクを2で割る
- とりあえずソースコードは以下
+ | fenwick_tree_bs.rb |
練習問題
AOJ DSL_3_C
フェニック木(区間の最小値)
解説(xxx)
CodeForcesに有志見つけた論文上げてた → How to use Binary Indexed Tree for Range Min/Max Query?
2.2 BITを定義する
フェニック木(左右どちらの形式の木構造にしても)は2のK乗のノードを持ち、その高さはKです。
もしその配列のインデックスをバイナリで管理するとしたら
- 左二項木(left binomial tree)であるところのBIT1は
- 親ノード(i) = i + 2のLSB(i)乗
- 右二項木(right binomial tree)であるところのBIT2は
- 親ノード(i) = i - 2のLSB(i)乗
def lsb(n) n&-n end # left def parent_l(n) n -= lsb(n) n end # right def parent_r(n) n += lsb(n) n end p parent_l(7) #=> 6 p parent_r(7) #=> 8
これにより、左右どちらの木構造にしても探索がlogNになる
(訳者注):いままで作ってたのは左二項木になる
2.3 クエリ操作
インデックスi, j、配列 1 <= i <= j <= N が与えられるとする。このときA[i], A[i+1], ... , A[j]のうち最小値が何か?という問いに答えたい。まずは最初の木のノードiから親を辿り始め、そのインデックスがj以下になるまでできるだけ処理を進める。同じことを2番目に用意した木で実施し、ノードjから親を辿る。どちらの場合でも、私たちは同じノードに至り、それにより配列はA[i ... j]という部分列に分けられる、これは用意した両方の木にあるし、探索が終了した共通のノードにも見つかる。
部分列A[5 ... 13]に対するクエリ操作により、これの例示をします。
ノード5から探索を始め、探索中のノードのインデックスが13以下になるまでそれを続けます。その次のノード8のインデックスは16で、これは13より大きいためそこで探索を終了します。ですので、ここで作成した部分列には14, 15, 16は含まれない。ここまでで、探索はノード5,6,8を通った。ここまでで2つ目の木にて見つかるノード5,6について最小の値を取得した。図2を見ると、ノード5はA[5]の最小値を保持しノード6はA[6 ... 7]までの最小値を保持する。同様にして、2つ目の木にてノード13から探索を開始し、ノード13,12,8を通る。先ほど1つ目の木にてノード13,12の最小値を取得したはずです。図1を見るとノード12はA[9 ... 12]の最小値を保持しノード13はA[13]の最小値を保持する。
ここで得られる観察としては、A[5 ... 13]という配列は以下のような部分列に分割された:
A[5 ... 5], A[6 ... 7], A[8], A[9 ... 12], A[13]
これの重要なところは、そのどちらの探索にもノード8が含まれていることです。これが常に起きることを証明します:(証明略)
まとめ
- 要は指定された範囲で両方の端から探索すると絶対最小値が見つかるようです
- 操作
min
min(left,right): 区間left〜rightまでの範囲における最小の区間の値を返す まず左手、次に右手、最後にBITと実際の値を比較して返す (1) val を無限で初期化 (2) インデックス(=idx)をleftで初期化 (3) インデックス(=idx)がright以下の限り,(a)以下をループ ...(a) val に @bit[idx] と valを比較して小さいものを上書き ...(b) i を 右二項木 の方法で親を辿り上書き (4) インデックス(=idx)をrightで初期化 (5) インデックス(=idx)がleft以上の限り,(a)以下をループ ...(a) val に @bit[idx] と valを比較して小さいものを上書き ...(b) i を 左二項木 の方法で親を辿り上書き (6) val と @array[i] を小さいものを上書き (7) valが区間最小値なのでリターン
- とりあえずソースコードは以下
+ | fenwick_tree_bs.rb |