本文共 1419 字，大约阅读时间需要 4 分钟。

先说树状数组最简单的用法，修改上面图中的某个点，并求某段区间的和；

第一个函数；

x&(-x);这个东西的由来就不说了。。。灰常奇妙啊。。

如果是x+=x&(-x);就是得到的改点的父节点的值；比如x=4时；就能得到8；

而x-=x&(-x)的话，就是得到x这个点的管辖区间的下个区间的管辖点；

比如说，x=7,代入后6；不断循环到0能依次得到 6.。。4.；

把他们所有的管辖区间正好是1....7；

int lowbit(int x)  //这个函数主要是用来求的是某个点管辖范围{      return x&(-x);  }

第二个函数

这个函数，是用来修改树状数组的；

如果是一般的算法只用修改改点就可；但是树状数组必须修改所有改点被管辖的区间；

比如把a数组的 a[2]减去1，（令N=16）；则所有2被管辖的点有4，8，16都应该减去1；

就是调用函数 update（2，-1）；

void update(int x,int num)  {      while(x<=N)       {           d[x]+=num;           x+=lowbit(x);       }  }

第三个函数

这个函数就是求区间和了。比如getSum（7）的话，就是求a[1]+a[2]+...a[7];

上面是最基本的用法；要学习树状数组必须把上面的过程原理搞明白；

搞明白d数组和原来a数组的区别

int getSum(int x)  {      int s=0;      while(x>0)       {           s+=d[x];           x-=lowbit(x);       }      return s;  }

树状数组的变形应用

<1> 每次修改的是一个点，所求的是关于某段区间；

这种情况最好办；比如说poj2352 stars；求每个点前面比他小的点的个数；

只用设置数组a[],先全是0，然后有某个点就依次修改，并以此统计；

这一种是最基本的向上修改，向下统计；（基本上都是。。。）

<2> 每次修改的是一个区间，所求的值是关于某个点的；

代表的典型题目是HOJ1556 color the ball；

这个题是每次修改了一整个区间，最后求的是每个点修改的次数；

     这个需要将上面的函数，稍加修改；

要向下修改，将它后面的区间都加一遍；

再向后修改，把不必要的修改区间再减去；

用他的父节点记录每个点的染色次数；

统计时需要

void update(int x,int num)  {      while(x>0)       {           d[x]+=num;           x-=lowbit(x);       }  }

这种修改一个区间，而求某个点的修改次数的，一般的都是向下修改，向上统计；

对于二维的情况，d[][]中的d[i][j]这个点也有他自己的管辖区间，从一维推广到二维；可以很容易理解；

一维情况是一段区间的管辖范围，二维就是一个矩形的管辖范围，而每一维可以独立考虑；

int getSum(int x)  {      int s=0;      while(x<=N)       {           s+=d[x];           x+=lowbit(x);       }      return s;  }

转载地址：https://blog.csdn.net/weixin_38960774/article/details/79405284 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！