浅谈树状数组及其应用

《浅谈树状数组及其应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈树状数组及其应用一、引言先由一道题冃引人（线段树的入门题冃）题目大意：给出一个数组A,有以下操作：Change（i,data）：把A［i］的值加上dataSum（i,j）：求区间［i,j］的和，并输出。题目分析：很容易就想到，直接模拟，开一个数组，改变值时就直接操作。求和时就把从i到j的值加起来，输出。但这种直观的做法显然十分不足，虽然对于change的操作很方便，但对于sum的操作就会消耗很多的时间。由于本题操作较多，所以这种做法在数据规模较大时就会超时。所以，就要求一种高效的算法。而线段树就能满足这种要求，用线段树的做法在这里就不详谈了（有兴趣

2、的可以自己想）。用线段树做的话，虽然change的操作的耗时升到了LogN,但sum的操作的耗时却同样降到了LogN,时间消耗分摊后就很低，是能够接受的。在这里，要介绍另一种做法一一树状数组。树状数组是一类比较简单的数据结构，和线段树比较像。树状数组是维护前缀和的一种数据结构。这就导致它能用较短的时间來实现查询和改变值。树状数组比线段树、平衡树要容易写，代码复杂度低。但不足的是适用面较窄。有句话是这样说的：能用树状数组的就能用线段树，能用线段树的就能用平衡树。所以一般都是能用线段树就不用平衡树，能用树状数组就不用线段树。（从这其实就可以対道树状数组的魅

3、力有多大了）二、树状数组介绍首先，先要理解树状数组的含义。含义其实就是用一个数组，构成树形结构來维护原数组的前缀和。观察下图（这个图也是网上经常出现的）:A1A2A3A4A5A6A7A8A9A10A为原数组，C为树状数组。同时，观查下表:十进制数对应的二进制数二进制数最右端第一个1的位置11121023111410035101161102711118100049100111010102显然，对于树状数组C,C[I]对应“管辖”多少个元素，与它对应二进制数最右端第一个1的位置有关。这样，就能够达到询问一个区间的值，或者改变值的时间代价为LogN.三、对于

4、树状数组的几个问题怎么查找一个数二进制数最右端第一个1的位置很容易就想到一种方法就是：LowBit(x)=xand((notx)+1)。对于数x,notx后就会对x的二进制数的每一位取反。+1后,改变的二进制数最右端第一个()就会变成1,而后而的1就会变冋0。但这个操作不改变前面的变化，所以再进行and操作时，就能够得到二进制数故右端第一个1的位置。由于notx=-x-1(这个是因为对于0和-0的补码不同所致)，那么求二进制数最右端第一个1的位置的式子就可以写成很简单的形式LowBit(x)=xand-Xo从V的位置改变值data：很容易就能想到的是，

5、因为树状数组是耍维护前缀和，那么改变一个值时，它影响的是后面的值。又由丁•某个树状数组中的元素是“管辖”一个区间的值；那么，这个值影响的是下一个“管辖区”，这个“管辖区”在哪呢？明显，其实就是v+LowBit(v),然后往后一直修改，到比数组的长度大的时•候停下来。以下为代码(n为树状数组的长度)：procedureadd(v,data:integer);beginwhilev

6、元素,那么只耍从这个“管辖区”，跳到前面的“管辖区”，把和加起來就是了：functionsum(v:integer):integer;vari:integer;begini:=0;whilev>0dobegininc(i,c[v]);v:=v-LowBit(v);end;cxit(i);end;对于树状数组，就只有这么些函数(所以代码就比较少)。但树状数组的神奇之处就在于这三个函数了。(本质只有两个)仅仅就是这三个函数，但这就是树状数组的看家本领了。用好这三个函数，也就能解决比较多的问题。那么，对于开头提到的题目，对于change(i,data)的操作

7、，直接就执行add(i,data)就可以了,对于sum(i,j)的操作，执行sum(j)・sum(i・l)就是了。四、树状数组的应用(一)数星星(pku2325)题目大意：给出一堆星星的坐标。一个星星的级别的定义为在它左下方星星的个数。输出各个级别星星的个数。题目解释：其实这题就是一道比较裸的数据结构题一一用线段树能够很好的解决掉。同样，用树状数组也能做出，而且非常漂亮。由于坐标本來就排好序，就更好做了。只需从左下角开始线性扫描一遍，然后按照星星的x坐标插进树状数组里。为什么这样呢？很明显，就好像把星星都压缩到一行，在左边的星星个数就好统计了。因为坐标

8、木來就排好序，那么对于一个星星，如果y坐标比它小的，那么肯定会先插到了数组里，那么综合起来，数