Binary Indexed Tree (Fenwick Tree)
コードについての説明
BIT(binary indexed tree) は1点加算と区間和のクエリを高速に処理することのできるデータ構造. Fenwick Tree とも呼ばれる.
Segment Tree を用いても実装できるが BIT の方が基本的に速い.
理由としては "メモリを 2 冪にそろえる必要がないこと(もちろん完全平衡二分木でないようなものに対しても Segment Tree を考えることはできるけど実装的にサイズは 2 冪で取ることが多い)",
"計算が非再帰かつビット演算を用いて遷移が可能であること",
"例えば $i$ 番目の要素に加算する場合にかかる計算量が数 $i$ の立っているビットの数に比例すること(Segment Tree では必ず $\Omega(\log n)$ 回かかる)" などがある.
説明はおそらく検索すればわかりやすいものがいくつも出てくると思うので他のかたにゆずることにする...
ブロックの持ち方をフィボナッチ数にすることで $\log$ の底が変わり計算量的には速くなるという話もある(参考). (実測はたぶん速くならないと思う)
時間計算量: 構築 $\O (n)$, 各クエリ $\O (\log n)$
コード
template<typename T> class BIT {
private:
int n;
vector<T> bit;
public:
// 0_indexed で i 番目の要素に x を加える
void add(int i, T x){
i++;
while(i < n){
bit[i] += x, i += i & -i;
}
}
// 0_indexed で [0,i] の要素の和(両閉区間！！)
T sum(int i){
i++;
T s = 0;
while(i > 0){
s += bit[i], i -= i & -i;
}
return s;
}
BIT(){}
//初期値がすべて0の場合
BIT(int sz) : n(sz+1), bit(n, 0){}
BIT(const vector<T>& v) : n((int)v.size()+1), bit(n, 0){
for(int i = 0; i < n-1; i++){
add(i,v[i]);
}
}
void print(){
for(int i = 0; i < n-1; i++){
cout<<sum(i)-sum(i-1)<< " ";
}
cout<<endl;
}
//-1スタート
void print_sum(){
for(int i = 0; i < n; i++){
cout<<sum(i-1)<<" ";
}
cout<<endl;
}
};
verify 用の問題
AOJ : Range Sum Query (RSQ) 提出コード