1.概念
给定一个n个数字的数列，要求一下操作：?
? ①改变第k个数字，增加或减少一个值；
? ②查询第i个到第j个数的和
?一般数组解法： O（1） O（n);
?树状数组 O（logn） O（logn）；
2.构建
假设给定数列A[1]->A[8]
?序列C[]为树状数组 特点：
（1）满二叉树，且二叉树中的每个叶子节点为A[]的一个元素 ? ? ? ? ? ?
?（2） C[i]为A[i]对应的那一列的最高的节点
找出规律：
i的二进制中从右到左连续0为x，则C[i]拥有2^x个叶子，C[i]为序列A[]中第i-2^x+1到第i个元素和，即C[i]=A[i-2^x+1]+…+A[i];
则S[i]:前i个元素的和
S[i]=C[i]+C[i-2x]+…
?***计算2^x:? 2^x=i&(-i) //位运算
证明：? i的二进制为A1B，其中B为全0序列。 ? ? ?
? ? ? ? ? ?假设A’为A的反码，B’为B的反码。 ? ? ? ? ? ?
? ? ? ? ? ? ? 由于补码=反码+1，-i=A’0B’+1。 ? ? ? ? ?
? ? ? ? ? ? ?因为B’为全1序列，-i=A’1B。 ? ? ? ? ?
? ? ? ? ? ? ?因此，i and (-i)=A1B & A’1B=1B，即2x的值。
int lowbit(int x){
return x&(-x);
}
int sum(int i){
int s=0;
while(i>0){
s+=c[i];
i-=lowbit(i);
}3.数据更新
x为i的二进制从右到左连续0的个数。
如果A[i]改变，则C[i]需要改变。
如果C[i]改变，则C[i+2x]需要改变。
void update(int k,int value){
while(i<=n){
c[i]+=value;
i+=lowbit(i);
}