树状数组
讲树状数组前需要有个大前提----lowbit（）函数
lowbit(x)是x的二进制表达式中最低位的1所对应的值
就比如说，6的二进制是110，所以lowbit(6)=2
在学树状数组前，我们要学会lowbit()函数常用代码写法：
下面我们学习用lowbit（x）来维护区间
大前提设节点编号为x，那么该结点维护的区间和是( x-lowbit(x)，x ]
假设二叉树有编号有x={1、2、3、4、5、6、7、8}，共8个结点//借助二叉树来分析
用数组A[1]、A[2]......A[8]储存，那么各个结点维护区间和 的区间(c[i])为：
c1维护区间(1-lowbit(1)，1]即(0,1] A1本身
c2维护区间(2-lowbit(2)，2]即(0,2] A1+A2
同理：c3维护(2,3] A3
c4维护(0,4] A1+A2+A3+A4
c5维护(4,5] A5
c6维护(4,6] A5+A6
c7维护(6,7] A7
c8维护(0,8] A1+A2+A3+A4+A5+A6+A7+A8
由此我们可以画出区间维护图为：
我们设C[i]代表子树的叶结点权值之和：
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
将C[i]数组的结点序号转化为二进制 1=(001) C[1]=A[1];
2=(010) C[2]=A[1]+A[2];
3=(011) C[3]=A[3];
4=(100) C[4]=A[1]+A[2]+A[3]+A[4];
5=(101) C[5]=A[5];
6=(110) C[6]=A[5]+A[6];
7=(111) C[7]=A[7];
8=(1000) C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
对照式子可以发现 C[i]=A[i-2^k+1]+A[i-2^k+2]+......A[i]; //区间和表示 （k为i的二进制中从最低位到高位连续零的长度）
如验证i=6,k=1。C[6]=A[6-2^1+1]+A[6-2^1+2]+..A[6] = A[5]+A[6]
lowbit(x) 就是取出x的最低位1,换言之lowbit(x)=2^k
那么我们可以得到一个重要结论：
C[i]=A[i-2^k+1]+A[i-2^k+2]+......A[i];
C[i]=A[i-lowbit(i)+1]+A[i-lowbit(i)+2]+......A[i];
之后我们结合二叉树性质来分析：
A[8]={1,2,0,1,3,0,2,1} //假定初值
C[i]表示存储的区间和（附上一张图）
由此我们可以推出四条重要性质：（最好结合图例，将其背过）
(性质1)每个内部结点C[x]保存以它为根的子树中所有叶结点的和。
(性质2)每个内部结点C[x]的子结点个数等于lowbit(x)的值。
(性质3)除树根以外，每个内部结点C[x]的父亲结点是C[x+lowbit(x)]
(性质4)树的深度为O(logN)
紧接着我们再来分析一下它的性质：
(性质1)每个内部结点C[x]保存以它为根的子树中所有叶结点的和。
这里就会运用到树状数组中一个重要的算法：查询前缀和（这里附上代码）
****当然，他还是有两个大前提的：
大前提(1) . lowbit(x)运算（上文已讲述）
大前提(2) . 树状数组处理的下标为1..n的数组，绝不能出现下标0的情况。因为lowbit(0)=0 陷入死循环
样例：x=5,求C[5] //即C[5]前缀和c1~c5之和
1循环： while(5>0) res=c[5]=a[5]=3 x=5-lowbit(5)=5-1=4 2循环： while(4>0) res=c[5]+c[4]=3+4=7 x=4-lowbit(4)=4-4=0 //循环结束，返回res=7
(性质3)除树根以外，每个内部结点C[x]的父亲结点是C[x+lowbit(x)]
这里就会运用到另一个算法：单点修改
样例:由上图n=8,x=5,y=10使a[5]+10区间修改过程:
循环1. while(5<=8) c[5]=3+10=13 x=5+lowbit(5)=5+1=6 //父编号
循环2. while(6<=8) c[6]=3+10=13 x=6+lowbit(6)=6+2=8 //父编号
循环3. while(8<=8) c[8]=10+10=20 x=8+lowbit(8)=16>n //循环结束
最后还剩一个区间和计算：sum(y)-sum(x-1)（此处不再多讲）
完美撒花！