前言
树状数组，又称二叉索引树，是一种代码简单，应用广泛的神奇数据结构！
普通树状数组
概念普及：树状数组的原理
设黑色框内数组为A[1]→A[8]
那么可以得到以下式子：
C[1] = A[1];
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[7]=A[7];
C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
我们便可以得到C[i]=A[i−2k+1]+A[i−2k+2]+...+A[i];
在这里，k为i的二进制中从最低位到高位连续零的长度
那么，如何求出二进制中从最低位到高位连续零的长度呢？
我们需要引入lowbit
inline int lowbit(int x)
{
return x&(-x);
}
&运算，即与运算，即按位比较都是1则为1，否则为0。
lowbit的原理简单说一下：
在计算机中二进制是以补码存储的。对于x(x>0),他的补码就是他的本身. 而 [−x]补为[x]补连同符号位取反加一之后的结果 所以[-x]补&[x]补刚好就是最低位1的结果
总结一下规律：x&(-x)，当x为0时结果为0；x为奇数时，结果为1；x为偶数时，结果为x中2的最大次方的因子。用处呢就是找最低位的1的位置。
那么我们树状数组的雏形就搭建好了，看看几个基础函数的用法吧。
add修改
inline void adds(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
t[i]+=y;
return ;
}
query查询
inline int query(int x)
{
int tot=0;
for(int i=x;i;i-=lowbit(i))
tot+=t[i];
return tot;
}
有了上面的模板，我们可以解决基础的实际性问题：
1.单点修改+区间查询
adds(x,y);//在第x个数上加y
query(y)-query(x-1);//求区间x~y的和（前缀和思想）。
【模板】树状数组 1
2.区间修改+单点查询
差分序列第一个数和原来的第一个数一样
差分序列最后比原序列多一个数，即最后一个数的相反数
差分序列求前缀和可得原序列
将原序列区间[L,R]中的元素全部+1，可以转化操作为差分序列L处+1，R+1处-1
根据规律3我们可以得到(s为差分前缀和数组,a为原数组，c为差分数组)
根据上文规律4我们可以得到区间修改代码(设区间为l，r)
adds(l,x),adds(r+1,-x);
query(x)//求出第x个数的值
【模板】树状数组 2
3.区间修改+区间查询
=a[1]+a[2]+a[3]...a[n]
=c[1]+c[1]+c[2]+c[1]+c[2]+c[3]...c[1]+c[2]...+c[n−1]+c[n]=c[1]+c[1]+c[2]+c[1]+c[2]+c[3]...c[1]+c[2]...+c[n−1]+c[n]