树状数组

树状数组常用于维护前缀信息，如前缀和、前缀乘积等等。

最常见的如给你一个长度为n的数组，单点修改，查询区间的和。

首先是想一下为什么不能用前缀和数组强行搞

先看一下前缀和

黄色和蓝色部分合起来表示前缀和覆盖的区间
黄色表示前缀和信息储存的位置

如果要修改a[5]还好…只有s[5]会受到影响，万一要修改a[1]或者a[2]的话就要修改s[1],s[2],s[3],s[4],s[5]，也就是全都要改。

这样的话时间复杂度就上天了。

用前缀和处理带修改的区间求和问题

操作的时间复杂度：

1、对一段区间求和O(1)

2、单点修改O(n)

发现算法瓶颈在于修改，考虑牺牲查询的时间复杂度，使得修改变快一点就好了。

造成这个问题的原因是前缀和数组所覆盖的长区间太多了，所以导致单点修改要把所有涵盖该点的区间信息全部更新一下。

也就是说我们现在要把这些很长的前缀和区间变得尽可能短，同时还得让它们能拼出任意一段前缀和。

二进制是一个很好的东西，原因在于二进制可以表示所有的数字，那么用长度为二进制整数的区间来储存区间和就能做到让非常长的区间数目尽可能的少，而且还保证能够拼出任意一段区间了。

所谓的“二进制整数”是指如1,2,4,8,16,32,64...这样 $2^k$ 的数。

树状数组结构如图所示现在保存的是一些二进制短区间，可以在log级别的操作下拼接出我们想要的前缀和，同时因为都是短区间，所以包含某个点的区间数会很少，这样每次修改单点时也不用修改太多的区间。

黄色和蓝色部分合起来表示树状数组所覆盖的区间
黄色表示树状数组信息储存的位置
黑色的线稍后解释作用

在树状数组中，第i个点储存了右端点为i，区间长度为lowbit(i)的区间元素和，也就是从i-lowbit(i)+1到i的区间和

Lowbit(x)表示求x在二进制下位最低的1连同后面的0所组成的数字，举个例子，6的二进制表示是110(2)，那么lowbit(6)=10(2)=2，也就是lowbit(6)=2

lowbit的求法与二进制补码有关。

计算机的CPU只能做二进制加法，不能做减法，但这并不意味着减法就没法做了，因为可以把减法转换为补码的加法

举个简单的例子，假设我们用8个二进制位来表示一个整数，其中第八位表示符号(0为正数，1为负数)。

虽然不知道下面这个数是几，但是我们先让这两个数字做一步加法。

00001010+11110110，结果是100000000，发现变成一个二进制9位数了，溢出了一位，因为这是一个8位有符号二进制数，这个溢出的第9位就被舍弃掉了。那么现在结果就变成了00000000，也就是十进制的0

10加上一个数字等于0，那这个是几呢，它当然是-10。所以下面这个二进制数是-10。

我们注意到红色部分就是我们想要找的lowbit值，而我们不需要的蓝色部分每一位都是相反的。

使用位运算&操作，就取出了一个数的lowbit。

int lowbit(int x)
{
    return x&-x;
}

先说查询吧，比如现在我需要查询1-x的前缀和
因为我们把每一段的区间信息都储存到右端点所在的位置了，所以只要一边合并区间信息，一边向左移动区间长度遍历经过的点，最终就合并出了1-x的前缀和

举个栗子来说，假设现在要查询s[7]，也就是a[1]+a[2]+a[3]+...+a[6]+a[7]。

c[7]储存了a[7]一个元素的和，所以下一个位置是c[7-1]

c[6]储存了a[5],a[6]两个元素的和，所以下一个位置是c[6-2]

c[4]储存了a[1],a[2],a[3],a[4]四个元素的和，所以下个位置是c[4-4]

到第0个位置，结束算法。

int sum(int pos)
{
    int ans=0;
    while(pos)
    {
        ans+=c[pos];
        pos-=lowbit(pos);
    }
    return ans;
}

现在再来说说修改，比如说现在我要修改a[5]，那么包含a[5]的区间都会受到影响。从图上看，如果要修改某个点的值，只需要沿着黑色的线一路向右上方向移动，依次修改经过的树状数组上的点即可。

问题在于如何实现一路向右上方移动的操作。

在原图的基础上加入一些绿色的线条

求和这个操作其实就是沿着绿色的线一路左上，把经过的点都加起来。绿色的线是查询时遍历到的节点。

而黑色的线是修改操作时需要修改的节点，黑色的线跟绿色的线是完全左右对称的。

也就是说查询操作每次向左移动lowbit，而修改操作只要向右移动lowbit即可。

void add(int pos,int x)
{
    while(pos<=n)
    {
        c[pos]+=x; 
        pos+=lowbit(pos);   
    }
    return;
}