查询和修改
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)
该结构满足以下性质:
- 每个内部节点 c[x] 保存以它为根的子树中所有叶节点的和。
- 每个节点
x管辖的区间长度 =lowbit(x)，范围是[ i−lowbit(i)+1,i ] 。 - 除树根外，每个内部节点 c[x] 的父节点是 c[x + lowbit(x)] 。
- 树的深度为 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，这样会陷入死循环。
)
