浅谈树状数组

今天药忘吃喽~ 2021-11-01 06:56 361阅读 0赞

今天，我来跟大家谈谈对树状数组的心得。树状数组是一个利用数组来模拟树的一种数据类型，它在特定的题目中可以用来代替树来提高效率。

不同于二叉树，树状数组的大致意思是这样的：（图片来自于王陸）

![1742044-20190716195601841-1245041989.png][]

子结点的1，2，3，4，5，6，7，8对应的是原数组的结构，而上面延伸出来的结点则代表着一段区间的区间和。

![1742044-20190716200208948-492259688.png][]

这时就要引入到一个函数lowbit，lowbit究竟是用来干什么的的呢？

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

这个函数可以帮助我们计算到下一步应该去到哪，其具体原理要看每个数字的二进制表示。先观察每一个结点的2进制树表示：

1=0001，2=0010，3=0011，4=0100，5=0101，6=0110，7=0111，8=1000。发现每要往上一个区间走时，1都会向左移一位。以1为例-1在计算机中表示为1111,1&(-1)+1=0010。利用lowbit可以快速帮我们计算出需要加减的值。这样，我们就可以在数组内模拟树的形式。

树状数组到底是用来干什么的呢？树状数组支持的是单点修改以及区间的和的查询。单点修改看起来好说，那么查询要怎么做呢？由于树状数组内i保存的是从1号位到i号位的和，显然区间\[x,y\]内的和应该是bit\[y\]-bit\[x-1\]。那么这样，查询i号为存储的值，就类似于单点修改的反向操作，是一次次向下走。

理解了lowbit，sum以及update之后，树状数组也就呼之欲出了：（在源代码中，我并没有写lowbit而是直接使用了i&(-i)）

#include<cstdio>
    using namespace std;
    #define kb 500010
    
    inline int read()
    {
        int ans=0, w=1;
        char ch=getchar();
        while(ch<'0' || ch>'9')
        {
            if(ch=='-') w=-1;
            ch=getchar();
        }                
        while(ch>='0' && ch<='9')
        {
            ans=ans*10+ch-'0';
            ch=getchar();
        }
        return ans*w;
    }
    
    int bit[kb];
    
    void update(int x, int k, int n)
    {
        for(int i=x; i<=n; i+=i&(-i)) bit[i]+=k;
    }
    
    int query(int x)
    {
        int ans=0;
        for(int i=x; i; i-=i&(-i)) ans+=bit[i];
        return ans; 
    }
    
    int main()
    {
        int n=read();int m=read();
        for(int i=1; i<=n; i++)
        {
            int ai=read();
            update(i, ai, n);
        }
        for(int i=1; i<=m; i++)
        {
            int k=read();int x=read();int y=read();
            if(k==1)    update(x, y, n);
            else        printf("%d\n", query(y)-query(x-1));
        }
        return 0;
    }

希望该博客能帮助到大家，如果有什么不懂的可以在评论区留言。

转载于:https://www.cnblogs.com/king-kb/p/11197232.html

[1742044-20190716195601841-1245041989.png]: /images/20211101/78f7d95f49dc41d9b70036dd605cf1e2.png
[1742044-20190716200208948-492259688.png]: /images/20211101/9a45c69da2b44814a8c7bf7bb105ecaf.png