Algoogle

Algorithm for Programming Contest

Binary Indexed Tree(Range Add)

基本情報


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

N := 区間の幅

解説


BITで区間に値を足すバージョン.
BITでやらなくてもSegment Treeでやればいいですが, BITを使って少し工夫するだけでいいので知っておくと便利です.

解説はBinary Indexed Treeのはなしの57ページ目あたりから読むとわかりやすいです.

コード


(bitr.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// t have +-*/ and 0
template<class T> class bitr {
public:

    bit<T> b, c;

    bitr(){}
    bitr(int N) {
        b = BIT<T>(N);
        c = BIT<T>(N);
    }
    // add x to [i,j) 
    void add(int i, int j, T x) {
        b.add(i,-i*x); b.add(j,j*x);
        c.add(i,x); c.add(j,-x);
    }
    // sum [0,i)
    T sum(int i) { return b.sum(i+1)+c.sum(i+1)*i; }
    // sum [i,j)
    T sum(int i, int j) { return sum(j)-sum(i); }
};

参考


問題


Comments