Binary Indexed Tree(BIT)について

2020/8/14　訂正
画像の8のbinary表現が1111になってました。1000ですね。
すみません。

備忘録：BITを理解し使えるようになる。

ABC174の問題を解く際にBITを用いました。今回はBITについて理解した点をまとめていきます。

１．概要

まず、ざっくりと概要を述べます。通常の配列では配列の1番目から8番目の要素までの和を出したいときには

for(int i = 0; i < 8; i ++) sum += v[i];

こんな感じで書くと思います。もちろん、これで合計値は計算できます。このときに、i = 0から i = 7まで8回のアクセスが必要となります。配列サイズが小さいときは良いのですが、配列が大きくなったらその分計算量が増えていってしまいます。このときの計算オーダーはO(N)となります。

この総和を求めるという操作をもっと効率よくできないかという要望を実現したのが、Binary Indexed Tree(BIT)やフェニック木(Fenwick Tree)と呼ばれる手法です。配列に要素を入れるんじゃなくて、要素と区間和をいい感じに入れてきます。この手法は元となるSegment Tree という手法を簡易化、高速化しており、とても簡単に実装できます。

詳しい構造は次から述べていきますが、配列の総和を求める操作をO(log N)のオーダーで計算することができます。ただし欠点として、i番目の要素を書き換えたいというときは、通常の配列なら1回のアクセスで済むのに、BITではアクセス回数が増えます。総和が簡単に求まることは、欠点を帳消しにするほどのメリットがあるみたいです。

２．構造

BITの構造を説明した後、BIT配列を生成します。

簡単のため、n=8でi番目の要素がiの配列を考えます。通常の配列だと

v_normal[] = {1, 2, 3, 4, 5, 6, 7, 8}

このように表現されるやつです。これをBIT化します。BITにする際には各インデックスを2進数表記にして、最下位の1が立っているビット（Least Significant Bit：LSB）以下の配列を足し合わせたものを、そのインデックスの要素とします。と言ってもわかりにくいので、図を用意しました。
2進数にする関係上、インデックスを1からはじめています。

結局のところ、

v_bit[] = {1, 3, 3, 10, 5, 11, 7, 36}

という配列になります。変な配列ですが、これが便利なんです。

次から総和と加算について説明をするのですが、その前に必要となるLSBの求め方について述べます。

３．LSBの求め方

次は総和と加算のために必要なLSBについてです。LSBはLeast Significant bitといって、1が立っている最下位のビットのことを呼びます。例えば、7だったら、

7 (10) -> 0111 (2) 

で、1桁目の1です。任意のnについてこれを一発で求めていきます。

そのために、2の補数表現を用います。2進数でマイナスの数を表す際の使われる方法の一つです。操作としては、0と1を反転させて1を足す。これだけです。7でやってみます。

7 (10) -> 0111 (2) -> 反転 -> 1000 -> -1を足す -> 1001 = -7 (10)

負の数が表現できたら、ビットごとの論理積をとってあげるだけです。

7    0111　
-7   1001

これの共通ビットを取るので、0001と求まります。

したがって、プログラムで実装する際は

7 & -7

とすれば、一発で求めることが可能です。「&」はビットごとの論理積を取得することができます。

LSBの準備ができたので、総和と加算について述べていきます。

４．総和

ようやく総和について述べていきます。総和の求め方は図で見ると一発で分かります。7までの和を求めます。

10 + 11 + 7 = 28

で１～７までの和になっているはずです。通常7回アクセスしないといけないはずが、なんと3回のアクセスで和を求めることに成功しました。

では、どの要素を足し合わせるかを機械的に求めていきます。これは、図で示した2進数表現を見れば簡単です。書き出してみると大きい順に

0111 -> 0110 -> 0100

となっています。つまり、現在のインデックスから一番小さい1を引けばよいのです。これは、先ほどやったLSBですね。したがって、i までの総和のプログラムは次のようになります。

for (int j = i; j > 0; j -= j & (-j))
{
  sum += v_bit[j];
}

分かってしまえば簡単ですね。n+1なのはbitはbinary表現の都合上、0インデックスを用いないためです。

５．加算

次に加算です。総和が簡単に求まる代わりに、加算には少し手間を加えます。と言っても、操作は総和とあまり変わりません。

ためしに、5番目に10を足します。図で見ていきましょう。

5番目が変化したら、影響のある6番目と8番目も更新する必要があります。通常の配列なら5番目を更新するだけでいいのですが、、、

どのようにして、6番目と8番目は更新が必要ですよとわかるのか、ということを考えます。と言っても、総和と似ています。2進数表現に注目です。

0101 -> 0110 -> 1111

ですね。これはLSBを足し合わせることで実現されます。プログラムにすると

//x : 加算する数
//n : インデックスの最大値（今回は8）
for (int j = i+1; i <= n; j += j&-j) {
   v_bit[j] += x;
}

こんな感じです。

今回はLSBを足しました。

６．さいごに

BITの説明をつらつらと書いていきました。今回はn=8と2^nの配列で説明しましたが、どんな長さの配列でも使用することができます。

F問題を調べているとき、セグ木（segment tree）やbitを使えば簡単みたいに、わかっていることが前提、頭の良い方に向けた解説が多く出てきたので、BITを基礎からまとめてみました。

理解の助けになったら嬉しいです。

また、誤りなどございましたらご指摘いただけると幸いです。