Fenwick Tree
BIT (Binary Indexed Tree)と呼ばれることも多いが、ACL では Fenwick Tree と呼ばれている。
機能はSegment Treeほど多岐にわたることは無く、一点加算と区間和が出来る。詳しくはSegment Treeの項で書くつもりなので(記事が出来上がったら)先にそちらを読んでほしい。
一点加算と区間和のそれぞれを、Segment Treeと同様に、配列長$ Nに対して時間計算量$ Ο(\log N)で行える。
しかし、空間計算量はSegment Treeより小さく$ Ο(N)になる。また、時間計算量も定数倍がかなり小さいため、実際には結構高速である。
主な使用用途
配列の転倒数を求める。(詳しいやり方は転倒数の記事を書く時にまた解説します) 座標圧縮してFenwick Treeに乗せると$ Ο(N \log N)で求められる。 これの最初の出力を求める部分までは本当にFenwick Treeやるだけ 別に負数を加算しても壊れないので、値を追加、削除、更に$ l以上$ r未満の値を数え上げみたいなことも出来るはず。
ただし、
もう set 内にある値は追加されない
まだ set 内にない値は削除されない
以上の$ 2点が必須条件になる気がする
以上の条件が満たされない場合は大人しく一点変更、区間和Segment Treeでやった方が良い
仕組み
indexを$ n-1だけずらした配列に現在の値を格納する
配列の$ 0, 1 \ldots, n-2番目の要素については、$ A_i = A_{2i} \oplus A_{2i+1}を格納する
というようにして、区間モノイド演算と一点更新を$ Ο(\log N)で達成していた。 https://scrapbox.io/files/61fabfb40372a4001dcbe2ef.png
ここで、加算演算が絡む問題といえば累積和というアルゴリズムがある。 累積和を活用すれば、$ [0, r)の和から$ [0, l)の和を減算して区間$ [l, r)の和を得ることができた。
Segment Tree上でも同様にすることで、区間演算クエリの左端を$ 0に固定することができたならば
https://scrapbox.io/files/61fac0f50df1f50023ff43ea.png
実はこの灰色の部分はいらなくなる。
(補足)
モノイドの定義からも分かる通り、Segment Treeで扱える演算全てが「逆」の演算、つまり補演算をもっているわけではない。加算は減算という補演算があるから、先ほど言ったように累積和から区間和の取得が出来るというだけであるので、注意されたい。 その点誤解されやすい表記になっていたので、ここに訂正しておく。大変失礼いたしました。
この灰色の部分を消すと、長さ$ 2以上の区間全てについてちょうど「その区間の右端にあたる位置」が空になる。
そこで、その部分にそれを入れると、Fenwick Treeが出来る。
https://scrapbox.io/files/61fac263d2eca3001d28786a.png
このため、クエリの時間計算量は$ Ο(\log N)のままだが、空間計算量は$ Ο(N)になる。
クエリの処理 : 区間和
一部先駆者の方々のサイトとは大きく異なる点として、半開区間で考えるので注意されたい。
また、以下Fenwick Tree上の$ i番目の要素を$ T_iと表記する。
先ほど述べた通り、区間$ [l, r)の和は、区間$ [0, r)の和から区間$ [0, l)の和を引いたものになる。よって、区間$ [0, r)の和と、区間$ [0, l)の和をそれぞれ求めればよい。
$ [0, k)の区間和を求めるには、以下のようにする。
答えをまず$ A=0としておく。
$ k \gt 0である間以下を繰り返す。
$ A = A + T_{k-1}とする。
$ kを$ 2進数表記した時に、重みが小さい方から見て最初に$ 1である場所だけを$ 0にした値を求める。$ kを、その値で置き換える。
$ [0, k)の区間和は$ Aに求められている。
なお、重みが小さい方から見て最初に……は、k -= k & -k とすると求められる。
例えば$ k=11としよう。操作によって
1. $ k=11なので、$ A = A + T_{10}とする。$ 11=0b1011なので、$ kは0b1010$ =10で置き換わる。
2. $ k=10なので、$ A = A + T_9とする。$ 10=0b1010なので、$ kは0b1000$ =8で置き換わる。
3. $ k=8なので、$ A = A + T_7とする。$ 8=0b1000なので、$ kは0b0000$ =0で置き換わる。
4. $ k=0なので終了する。
最終的に、$ A=T_{10} + T_9 + T_7となっている。これを各要素が表す元の数列の値に置き換えてみる。
元の数列の値を$ B_1, B_2, \ldots, B_Nとすると、
$ T_{10} = B_{10}
$ T_9 = \Sigma_{i \in 8: 9}B_i
$ T_7 = \Sigma_{i \in 0:7}B_i
となるので、結局$ A=\Sigma_{i \in 0:10}B_iと整理できる。
なお、時間計算量については、以下の通り。
「$ k \gt 0である間以下を繰り返す。」のループは、必ず$ kを$ 2進数表記した時の桁数$ = \log_2 k回以下で終了する。
それを$ 2回行うだけなので、区間和取得の計算量は$ Ο(\log N)となる。
クエリの処理 : 一点更新
区間和取得と比べて全く逆向きに考えることになる。
$ k番目の要素に$ xを加算することを考える。
まず、$ T_k = T_k xとする。
次に、$ T_kを内側に含むような区間を小さい方から全部見て、それらにも$ xを加算するのだが、これは先ほどとは逆に
$ kを$ 2進数表記した時に、重みが小さい方から見て最初に$ 0である場所だけを$ 1にした値を求める。$ kを、その値で置き換える。
ことによって$ kに求められる。
例えば$ k=9とすると、$ k=9, 11, 15と遷移する。$ T_{9, 11, 15}は、いずれも本来の数列における$ 9番目の要素を含む区間に対応する要素である。(ついでに言うと、この$ 3つだけしかない。)
これに関しても、区間和取得と同じような論理で時間計算量が$ Ο(\log N)であることを示せる。
発展的話題
一部の問題を非想定解で殴るのに使えたりする。
RAQ BIT
内部的に BIT を$ 2本持つことで、
Range Add Query BIT : 区間加算に対応している Fenwick Tree というものを作る事が出来る。
Lazy Segment Treeで同様のことをやろうとすると区間幅を持たせる必要があり、構造体を宣言してそれをatcoder::lazy_segtreeに渡すような形になる。これが期待を裏切らない面倒くささなので個人的には RAQ BIT を作ることを推奨したい。
2D BIT
BIT に BIT を乗せるという暴挙を行うことで、BIT の大きさ$ H, Wに対して、一点加算と(長方形のカタチをした)区間和取得を$ Ο(logH \cdot logW)で行う事が出来る。