暑假集训--树状数组

我们知道，要求区间 [ l , r ] 的和可以通过 [ 1 , r ] - [ 1 , l - 1 ]得到。

把这个思想应用到线段树上可以得出右儿子的信息 = 父亲 - 左儿子。

查询

复杂度O(logN),例如求1~7的和，可以通过4 6 7这三个结点的信息得出结果。

 1 int a[maxn];
 2 inline int lowbit(int x) { return x & (-x);}
 3 void add(int x, int d) {
 4     while(x <= n) {
 5         a[x] += d;
 6         x += lowbit(x);
 7     }
 8 }
 9 int sum(int x) {
10     int s = 0;
11     while(x) {
12         s += a[x];
13         x -= lowbit(x);
14     }
15     return s;
16 }

View Code

(未完