数据结构之树状数组.pptx

《数据结构之树状数组.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构之树状数组（BinaryIndexedTree）北京理工大学ACM集训队陈翔问题的引入：给定n个数，a[1]..a[n]。每次我们可能有两种操作：（1）求出a[i]..a[j]的和；（2）给a[x]的值加上一个值val。n的规模如果比较大（约100000）该如何高效的实现？树状数组看图形回答问题：（1）C数组是用于求和的，想想，每个C[i]求的是哪几个数的和？（2）整个图形像是棵树，每个节点会有几个孩子？（3）每个孩子节点向上的，直接父亲节点是哪个节点？提示：看每个数字的二进制码！大家一起来解答：（1）C[

2、i]记录了哪些数的和？0001C1=a10010C2=a1+a20011C3=a30100C4=a1+a2+a3+a40101C5=a50110C6=a5+a60111C7=a71000C8=a1+a2+a3+a4+a5+a6+a7+a8…………结论：第x个数，记录了x&（-x）个数！即C[x]=a[x-（x&（-x））+1]+…a[x]intgetsum(intx){//求1..x的和intsum=0;for(;x>0;x-=x&(-x))sum+=C[x];returnsum;}有时亦用:lowbit(x)表示

3、x&(-x)大家一起来解答：（2）每个节点会有几个孩子？lowbit(x)表示x&(-x)对于每个数x，它的孩子数就是这个循环次数，也就是lg(lowbit(x))个。for(j=1;j

4、函数于是乎，最前面提到的问题就完美解决了。初始化C数组全为0，然后针对每次操作，操作(1)：update(x,val);操作(2)：getsum(x)。树状数组时间复杂度O(nlgn)，简洁高效！学完了树状数组的基本操作，下面来看看树状数组可以发挥的强大作用吧！问题：树状数组的最基本功能就是求比某点x小的点的个数(这里的比较是抽象的概念，可以使数的大小，坐标的大小，质量的大小等)比如给定个数组a[5]={2,5,3,4,1}，求b[i]=位置I左边小于等于a[i]的数的个数.此例中b[5]={0,1,1,2,0}。

5、解决方案：直接遍历遍数组，每个位置先求出getsum(a[i])，然后再修改树状数组update(a[i],1)即可。当数的范围比较大时需要进行离散化，即先排个序，再重新编号。如a[]={10000000,10,2000,20,300}，那么离散化后a[]={5,1,4,2,3}。明白上面的后，就可以稍稍的应用下了。POJ2299题目大意：给n个数，a[1]..a[n]。如果a[i]>a[j]&&i

6、的时候，先看看数组里有多少比它小的，然后再更新。POJ2352题目大意：给n个*，每个*都一个坐标（x,y)，问对于每个*，其左下方共有多少个*（包含左下方同行，同列的*）对y坐标从小到大排序，如果y相同，就暗x坐标从小到大排序。相当于按x轴建立一维树状数组，然后求相当于它前面比它小的个数即可。问题的拓展：如果要求b[i]=位置i左边大于等于a[i]的数的个数，应如何处理呢？当然我们可以离散化时倒过来编号，但有没有更直接的方法呢?答案是有的。假设树状数组的上限值为MN。对于值是x的数，我们在更新时更新MN+1-x的

7、值。查询相应地改为getsum（MN+1-x）前面的问题相当于是“改点求段”型，即修改某一个点的值，再求某个区间的和的情况。如果，我们要分析的是“改段求点”型，即修改某一个区间，使其每个值都加上值val，然后再去询问你某个点的值是多少。问题的引入：给定n个数，a[1]..a[n]。每次我们可能有两种操作：（1）将a[i]..a[j]的每个数都加上一个值；（2）查询a[x]的值。n的规模如果比较大（约100000）该如何高效的实现？令del[i]表示i..MN段被加了多少。则区间修改[a,b]时，我们让del[a]+

8、+,del[b+1]--即可。（此时树状数组是建立在del数组基础上的）这个时候，要求某一个位置x的数的值时，用Getsum(x)来表示。（即a[x]=sigma(del[1]..del[x]))问题的深入：现在，我们如果可以对原数组中，进行区间的修改，想了解区间的和，该如何去做？提示：建立两棵树状数组del[i]依旧表示i..MN段被加了多少。我们想知道区