关于树状数组（略）

查询和修改

long long ask(int x) {//查询a[1]+a[2]+...a[x]的值 long long ret = 0; for (int i = x; i; i -= lowbit(i)) ret += C[i]; return ret; } void add(int x, int d) {//将 x 增加 d for (int i = x; i <= n; i += lowbit(i)) C[i] += d; }

查询是减法，因为分解；修改是加法，因为包含这个数的所有数（范围内）都要随之改变。

注意：

• lowbit(i)=i & (-i)（保留二进制最低位的1）
• 管辖范围=[i - lowbit(i) + 1, i]
• 区间长度=lowbit(i)

该结构满足以下性质:

1. 每个内部节点 c[x] 保存以它为根的子树中所有叶节点的和。
2. 每个节点x管辖的区间长度 =lowbit(x)，范围是[ i−lowbit(i)+1,i ] 。
3. 除树根外，每个内部节点 c[x] 的父节点是 c[x + lowbit(x)] 。
4. 树的深度为 O(logN) 。

1.对某个元素进行加法操作
树状数组支持单点增加，意思是给序列中的某个数A[x]加上y，同时正确维护序列的前缀和。根据上面给出的树形结构和它的性质，只有节点x及其所有祖先节点保存的区间和包含A[x]，而任意一个节点的祖先至多只有logN个，我们逐一它们的值进行更新即可。下面的代码在O(logN)时间内执行单点增加操作。

void update(int x, int y) { for (; x <= N; x += x & -x) c[x] += y; }

另一种写法

void update(int x, int y) { while(x<=n){ c[x]+=y; x=x+(x&-x); } }

2.查询前缀和
树状数组支持查询前缀和，即序列A第1至x个数的和。按照我们刚才提出的方法，应该求出x的二进制表示中每个等于1的位，把[1，x]分成O(logN)个小区间，而每个小区间的区间和都已经保存在数组c中。下面的代码在O(logN)时间内查询前缀和。

int sum(int x) { int ans = 0; for (; x; x -= x & -x) ans += c[x]; return ans; }

另一种写法

int sum(int x) { int ans = 0; while(x>0){ ans+=c[x]; x=x-(x&-x); } return ans; }

若求sum(7) = c[7] + c[6] + c[4]

3.统计A[x]...A[y]的值
调用以上的sum操作：sum(y) - sum(x - 1)

4.注意事项
要注意树状数组能处理的是下标为1..n的数组，绝对不能出现下标为0的情况，因为lowbit(0) = 0，这样会陷入死循环。