【自称】世界一分かりやすいBITの解説
こんにちは！一ヶ月ぶりのブログ更新です～今度はBITを解説しに行きます。実は一年前ほど研究室でBITとセグツリーを解説しましたが、あの頃解説はちょっと不明なところもあったので、このブログのきっかけになります。
BITはRSQ問題を解決するデータ構造で、O(logn)の計算量で区間の要素の総和を求められる。そして単独な要素をO(logn)計算量で更新できる。一回だけある区間の総和を求めるなら、愚直に足し合わせるだけで済みますが、もし数万回異なる区間の総和を問われったら、BITは凄く早い。
BITの基本概念は分割統治
一番簡単な考え方は区間を二つの部分区間に分けて、それぞれ総和を管理する。ある区間の総和を求めるとき、部分集合の総和を加算して素早く求まる。でも、区間総和の特徴を考えれば、本当は二つの部分区間の総和を記録する必要はない。
例えば、区間[1,8]上の総和と[1,4]上の総和が知ったら、[5,8]の総和は[1,8]の総和から[1,4]の総和を引けば求まる。だから、BITが管理する各区間は下図に示したようになる。
配列のインデクスで区間を決める
BITは処理を単純化するため、長さが２のべきの区間だけを扱える。つまり、区間の長さが1、２、４のような区間ばっかです。インデクス1からこうスペース空けて区間を配置していく。区間の右側はそれぞれ違うので、一次元配列で表現できる。配列のi番目のはiを右側とする区間の総和を格納する。
そして、i番目の要素が管理する区間の長さは必ずiの因数の中で一番大きい2のべきだ。これからそのことを証明して行く。簡単な例で説明する。12は二進数表現で00001100になる。もしこれを参照としてBITをアクセスしたら、長さ4の区間[9,12]の総和は得られる。それはなぜでしょうか？2のべきは二進数で表現したら、一ビットだけが1になる。2のべきである最大因数はiを二進数に変換したら、最下位の1まで切り取って得られる。12の場合区間の長さは4で、二進数表現は00000100になる。4は12の中に三個含まれる。１や２は12に偶数個含まれる。
前説明したが、BITはそれぞれの長さの区間をスペース空きで配置する。偶数番目の区間は飛ばされるので、iは必ず奇数番目の区間を管理する。こうして、証明できた。これから実用篇に入ります！
区間の長さを求める
i番目要素は長さがi&-iの区間を管理している。証明は単純なのでこのことは読者に証明してもらう。i&-iをlen(i)と呼ぶ。
BITの構築
BITを構築する時はまず配列で累積和を求める。i番目に1からiまでの要素の総和を入れる。でもそれじゃ余計な部分も入ってしまうので、その余計な部分を引く必要がある。i番目の要素は[i-len(i)+1,i]を管理する。それて、[1,i-len(i)]の部分は余計だ。その部分の総和は今i-n番目の要素だ。それて、配列の後ろから頭へスキャンしてn個前の要素を引けばBITを構築できる。
BITで1からiまでの総和を求める
[1,i]までの総和を求めるには、まず[1,i-len(i)]の総和を再帰的に求める。その結果をBIT配列のi番目の要素に足すと結果になる。例え[1,13]の総和を求める時に、順次に[1,12]、[1,8]の総和を求めていく。従ってO(logn)で求まることはわかる。
[1,i]の総和を求めれば、[l,r]の総和を求めるのも簡単だ。[1,r]から[1,l-1]を引けばわかる。
ある要素を更新
i番目の要素を更新したとき、i番目の要素を含む区間も更新されるべき。BITのi番目要素を更新した後、再帰的にi+len(i)番目を更新する。一番目の要素を更新するビジュアルを作った。
待ちくたびれたコードセッション
このセッションは作成したコードを上がる。コンテストなどで利用することはできる。
template<class T>
void build(T arr[],T bit[],unsigned int n){
bit[0]=0;
for(auto i=2u;i<n;i++) bit[i]=bit[i-1]+arr[i];
for(auto i=n-1;i>0;i--) bit[i]-=bit[i-(i&-i)];
}
template<class T>
void update(T bit[],unsigned int n,unsigned int index,T diff){
for(auto i=index;i<n;i+=(i&-i)) bit[i]+=diff;
}
template<class T>
T prefix(T bit[],unsigned int bound){
T ret=0;
while(bound>0){
ret+=bit[bound];
bound-=(bound&-bound);
}
return ret;
}
template<class T>
T query(T bit[],unsigned int l,unsigned int r){
return prefix(bit,r-1)-prefix(bit,l-1);
}
BITが解決できる問題
AOJ DSL_2_B 直接解決できる問題はRSQ問題で、BITだけで楽勝だ！
ABC 174F Range Set Query 異なる色が出現するところを1にして、ある区間に出現した色の種類はBITで集計できる。
