树状数组实现

叁歲伎倆 2022-05-12 02:44 161阅读 0赞

树状数组能够完成如下操作：

给一个序列a0-an

计算前i项和

对某个值加x

时间o(logn)

注意：有人觉得前缀和就行了，但是你还要维护啊，改变某个值，一个一个改变前缀和就是o(n)了。

线段树树状数组的题就是这样，维护一个树，比较容易看出来。

线段树：

[https://blog.csdn.net/hebtu666/article/details/82691008][https_blog.csdn.net_hebtu666_article_details_82691008]

如果使用线段树，只需要对网址中的实现稍微修改即可。以前维护最小值，现在维护和而已。

注意：要求只是求出前i项，而并未给定一个区间，那我们就能想出更快速、方便的方法。

对于任意一个节点，作为右孩子，如果求和时被用到，那它的左兄弟一定也会被用到，那我们就没必要再用右孩子，因为用他们的父就可以了。

这样一来，我们就可以把所有有孩子全部去掉

把剩下的节点编号。

![960a304e251f95ca5e588459cf177f3e660952ab.jpg][]

如图，可以发现一些规律：1，3，5，7，9等奇数，区间长度都为1

6，10，14等长度为2

........................

如果我们吧编号换成二进制，就能发现，二进制以1结尾的数字区间长度为1，最后有一个零的区间为2，两个零的区间为4.

我们利用二进制就能很容易地把编号和区间对应起来。

计算前i项和。

需要把当前编号i的数值加进来，把i最右边的1减掉，直到i变为0.

二进制最后一个1可以通过i&-i得到。

更新：

不断把当前位置i加x，把i的二进制最低非零位对应的幂加到i上。

下面是代码：

思想想出来挺麻烦，代码实现很简单，我都不知道要注释点啥

向发明这些东西的大佬们致敬

int bit[MAX_N+1]
    int n;
    
    int sum(int i)
    {
        int gg=0;
        while(i>0)
        {
            gg+=bit[i];
            i-=i&-i;
        }
        return gg;
    }
    
    void add(int i,int x)
    {
        while(i<=n)
        {
            bit[i]+=x;
            i+=i&-i;
        }
    }

[https_blog.csdn.net_hebtu666_article_details_82691008]: https://blog.csdn.net/hebtu666/article/details/82691008
[960a304e251f95ca5e588459cf177f3e660952ab.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/c0%3Dbaike80%2C5%2C5%2C80%2C26/sign=08d4c8271c4c510fbac9ea4801304e48/960a304e251f95ca5e588459cf177f3e660952ab.jpg