树状数组
今天听老刘讲了下树状数组，再结合自己的理解。补一篇学习笔记。
树状数组的用处：
1.单点修改+区间查询（本质）
2.区间修改+单点查询
3.区间修改+区间查询
当我们需要频繁的修改查询时，借用树状数组可以大大降低复杂度。（o（logn））
而且树状数组较线段树的好处就是：代码简洁。（能让你深切感受到二进制之美）
下面就来介绍一下如何构造使用树状数组。
预备知识（lowbit）
给你一个数，其转化为二进制从右往左到第1个1的值就是这个数的lowbit值。
eg：12（1100）的lowbit值即为4（100）
那么，lowbit（x）要怎么去计算呢？
首先我们把x取反+1，这样得到的（~x+1）与之前的x相比只有第一个1（从右往左）的后面的数相同了。
所以lowbit（x）=x&（~x+1）
由于计算机存储的采用是补码，所以~x+1=-x，那么lowbit（x）=x&-x
单点修改+区间查询
给出一个长度为n的数组，完成以下操作：
1.将第x个数加上k
2.输出区间[l,r]内每个数的和
如上图所示，原数组设为a，树状数组设为t。
t[1] (0001)=a[1] (0001);
t[2] (0010)=a[1] (0001)+a[2] (0010);
t[3] (0011)=a[3] (0011);
t[4] (0100)=a[1] (0001)+a[2] (0010)+a[3] (0011)+a[4] (0100);
以此类推。
以这样的方式来存储数组的数据结构其实就是树状数组了。
可以发现，t[x]管理的a[x]的数量取决于lowbit（x）
而现在我们要求sum（4），其实就是t[4]的值。
sum（6）（0110）=t[6]（0110）+t[4] （0010）
sum （7）（0111）= t[7] (0111) + t[6]（0110）+t[4] （0010）
又可以发现，我们要求sum(x)，只要从x开始不断减去lowbit(x)，就能还原整个管理区域。这样就保证了
sum（x）的复杂度最多是logx。也是为什么使用树状数组的原因。
那么当我们要进行单点更新时，不光要将t[x]+k，还要将管理x的t都加上k，也就是sum的逆向，不断加上lowbit（x)就行了。
贴下板子（非常的简洁哟）：
|
|
tip：树状数组下标不能从0开始，会陷入死循环）
区间修改+单点查询
在这里要引入差分数组d。（即a[]每个元素的增量）
eg：a[1]=1,a[2]=2,a[3]=0
d[1]=a[1]=1, d[2]=a[2]-a[1]=1 ,d[3]=a[3]-a[2]=-2;
那么当我们要做区间[l,r]修改+k时，由于这个区间内的差量是不发生变化的，变化的仅有边界的地方。
因此只要对b[l]+k,b[r+1]-k就能维护区间了。
当我们要查询单点时，可以发现a[x]= $\sum_{i=1}^x {d[i]} \quad$
这样就把单点查询变回上面的区间查询了。
因此我们只需要用树状数组来维护d这个差分数组就行了。
代码就不贴了，因为和上面的那一份是一模一样的。只要刚开始把bit[n]初始化为差分数组即可。
区间修改：对[l,r]的区间+k add（l,k) ,add(r+1,-k);
单点查询（x）：a[x]=sum(x);
区间修改+区间查询
区间修改的方式还是可以参照上面差分数组的方法。
区间修改：对[l,r]的区间+k add（l,k) ,add(r+1,-k);
着重来讲一下如何进行区间查询
上面讲了单点查询的方法。
那么不难想到位置p的前缀和：$\sum_{i=1}^p {a[i]} \quad=\sum_{i=1}^p {\sum_{j=1}^i {d[j]} \quad} \quad$
在等式右侧，d[1]被用了p次，d[2]被用了p-1次；
于是可知：
$\sum_{i=1}^p {\sum_{j=1}^i {d[j]} \quad} \quad=\sum_{i=1}^p {d[i]} \quad*(p-i+1) =(p+1)*\sum_{i=1}^p {d[i]} \quad-\sum_{i=1}^p {d[i]*i} \quad$
那么我们接下来只要用两个树状数组去维护d[i]和 d[i]*i 就好了。
c1[i]=d[i];
*c2[i]=d[i]i;
区间查询（l，r）：sum（r）- sum（l-1）
贴下代码吧：
|
|