BIT
一般には$ N 個の要素があり、任意の$ i 番目の要素の更新と、区間$ [1, i] の総和がどちらも$ O(\log N) でできるようなデータ構造である。イメージとしてはセグメント木と同様に区間を半分ずつにして、各区間の総和を記憶しておく。ただし、セグメント木と異なり、右側の分岐については区間を保持しない。すると、各区間の番号とその区間の終端の要素番号が一致することになる。たとえば下図で区間$ [1, 5] の総和を知りたいときは区間$ 4 ,5の和を求めればよい。これは区間番号の$ 2進数表記のLSBを反転させた区間の和を足していく操作に等しい。一方、$ i番目の要素を更新する場合はまず区間番号が$ iの区間の総和を更新し、そのLSBに$ 1を足した区間にも順次更新をかけていけばよい。 https://gyazo.com/18c890f3bc1bbbd3d1fc5230c7751c42
以上から、BITの実装は以下のようになる。なおindexのLSBに$ 1が立っている値はindex & -indexで求められることに注意。
code:java
public int query(int index) {
int res = 0;
while (index > 0) {
index -= index & -index;
}
return res;
}
public void add(int index, int value) {
while (index < a.length) {
index += index & -index;
}
}