浅谈树状数组和线段树
树状数组
类比：
其实可以把树状树组简单的看成一个帮你求前缀和的树组，add为单点修改值，query(x)即为询问1到x的前缀和的值。（至少我是这样看的）。
简介：
树状数组和线段树具有相似的功能，但他俩毕竟还有一些区别：树状数组能有的操作，线段树一定有；线段树有的操作，树状数组不一定有。但是树状数组的代码要比线段树短，思维更清晰，速度也更快，在解决一些单点修改的问题时，树状数组是不二之选。 取自OI-Wiki
数状数组通常用于区间修改以及区间查询。
原理：
黑色的数组表示a[i]，即初始的数组，红色的数组表示c[i]，即对应的树状数组。
$ c[i]=a[i-2^k+1]+a[i-2^k+2]+…+a[i] $ //k为i的二进制中从最低位到最高位连续零的长度。
i的二进制表达式中最后的一个1与后面的零组成的数即为c[i]所存储的数的个数。
存的个数从自身开始往前数，例如6=0110,10=2,c[6]存储了2个数，即为a[5],a[6];
例如：
$ 1\,0001\, c[1]=a[1] $
$2\, 0010\, c[2]=a[1]+a[2]$
$3 \,0011 \,c[3]=a[3]$
$4 \,0100 \,c[4]=a[1]+a[2]+a[3]+a[4]$
$5 \,0101 \,c[5]=a[5]$
$6 \,0110 \,c[6]=a[5]+a[6]$
$7 \,0111 \,c[7]=a[7]$
$8 \,1000\, c[8]=a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]$
1的二进制数为0001，最后一个1与后面的零组成的数为1，所以只存储一个数，即本身。
2的二进制为0010 ，二进制10为2，所以c[2]存储两个数，即本身即前一个数a[1]+a[2]。
3为0011，1，存储本身
4为0100，100，存储4个数
以此类推
总而言之就是以一种二进制的方式来存储一部分的值，原理讲得差不多了，先来看看树状数组的好处。
举例：
求1到第88这个数的和：
$88=1011000$
1000=8
10000=16
1000000=64
因此ans=c[88]+c[88-8]+c[88-8-16]+c[88-8-16-64] \, (c[0]无意义)
ans=c[88]+c[80]+c[64]
c[88]存储了8个数字,a[88],a[87]…a[81]
1011000-1000=1010000
10000=16
c[80]存储了16个数字，a[80],a[79]…a[65]
1010000-10000=1000000
1000000=64
c[64]存储了64个数字,a[64],a[63],a[62],a[61]…a[1]
因此ans=c[88]+c[80]+c[64]，可以看到查询的效率大大提升，原本要从1开始加到88，而现在只需要查询3个值，c[88],c[80],c[64]，这就是数状数组的优点所在了。
当然，只看查询的话，树状数组还不如直接用前缀和(看到前缀和就想到数学刚上的数列求前n项和)，但是还有区间修改或者单点修改，都是前缀和处理不了的情况。
实现：
那么要怎么样才能快速的取出数的最后一位1呢，这里我们引入一个函数 lowbit（）
我们知道计算机中是用原码，反码，和补码来存储数字的，这里引入一个概念，负数的补码表示即为该数的正数的反码后加1(例如：-88的补码即为88的反码加1)
88： 01101000
-88：
10010111+
00000001
10011000
所以,88&-88=0b(1000)=8
总而言之，x&-x就可以求出该数的最后一位1所在的位置。
int lowbit(int x){
return x&-x;
}接下来的add操作，将树状树组更新。
void add(int x,int k){//将每个a[i]加到对应的c[]，可以自己手动模拟一下
while(x<=n){
c[x]=c[x]+k;
x+=lowbit(x);
}
}query操作即为求1到x的前缀和。
int query(int x){ //求a[1]+a[2]+..a[x]的和
int ans=0;
while(x){
ans=ans+c[x];
x=x-lowbit(x);
}
return ans;
}总结：
数状树组代码较短，易记。
