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

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

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

 

  这时就要引入到一个函数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
     
      using namespace std;#define kb 500010inline 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;}
     

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