Algoogle

Algorithm for Programming Contest

Binary Indexed Tree

基本情報


計算量
用途 区間の和を求める. 値を加える.

N := 区間の幅

解説


BIT(Binary Indexed Tree)は区間の和を求めるのと1つの場所の値に加算するのををO(log N)で行えるデータ構造. 実現にビットを用いていて実装が非常に楽.
値の加算はi番目の値に加えたい場合は立っているビットの最後のビットを繰り上げていきながらその経路全てを更新する.
和の計算は0からi-1番目までの値の和の場合, 立っているビットの最後のbitを0にしながらその経路全ての和を返す.

コード


(bit.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// T have +-*/ and 0
template<class T> class bit {
public:
    vector<T> dat;
    int N;

    bit(){}
    bit(int N) : N(N) { dat.assign(N,0); }
    // sum [0,i)
    T sum(int i){
        int ret = 0;
        for(--i; i>=0; i=(i&(i+1))-1) ret += bit[i];
        return ret;
    }
    // sum [i,j)
    T sum(int i, int j) { return sum(j) - sum(i); }
    // add x to i
    void add(int i, T x) { for(; i < N; i|=i+1) bit[i] += x; }
};

参考


問題


Comments