树状数组(二叉索引树)理解与分析

《树状数组(二叉索引树)理解与分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树状数组（二叉索引树）理解与分析文/龚健飞说起树状数组，或许很多人会对这个名称或者这个概念感兴趣。但仅仅通过文字上的描述，初学者会比较难地理解到这个数据结构这个算法。我凭自己的认识来阐述一下对这个数据结构的理解，希望给其他初学者一个参考的同时也给自己一个机会更好地认识它。引言先用一个问题来引导出树状数组的概念。给定一个n个元素的的数组，对其进行操作。按照情况，sum(n)表示计算的和，add(x,d)表示让加上d。显然，对于第一种操作，利用较为简单的前缀和数据可以在O(1)的时间内解决单次问题。但

2、对于第二种操作，前缀和在n足够大的情况下显得无能为力。那么，树状数组能否解决这个问题？要回答这个问题首先得弄清，什么是树状数组。树状数组树状数组，顾名思义，即是将所有的数据排列成一棵树的形式，利用分支和源头（更确切地讲，是tree。）掌握数据信息以及进行操作，体现了一点分治的思想。要特别指出，排列成树的依据并不是数据本身，而是数据的索引，即是index。程序如下：#includeusingnamespacestd;inta[10000];intc[10000];intn;int

3、lowbit(intx){returnx&-x;//求出lowbit}intsum(intx){intret=0;while(x>0){ret+=c[x];x-=lowbit(x);}ret+=c[0];returnret;//求和函数}voidadd(intx,intd){while(x<=n){c[x]+=d;x+=lowbit(x);//加法操作}}intmain(){cin>>n;for(inti=0;i>a[i];c[0]=a[0];for(inti=1;i

4、+i){for(intj=i-lowbit(i)+1;j<=i;++j)c[i]+=a[j];//预处理}intch;cout<<"selecttheoperation"<>ch){if(ch==1){intx;cin>>x;cout<>x>>d;add(x-1,d);}cout<<"selecttheoperation"<

5、<<"1forsum"<

6、。加上位运算是直接基于二进制表达式的，更加接近计算机底层，所以执行起来比普通的加减法还要快。好了，且看lowbit的真正意义。按照上面的定义，38288的二进制是1001010110010000所以lowbit(38288)=10000（二进制）=16（十进制）。至于程序中，为什么x&-x能够获得x的lowbit呢？计算机里的负数采用补码表示，即-x实际上是x按位取反，然后加上1的结果。以下详细理解这句话。补码我们知道，在计算机内部数是由二进制表示的。现在一般的电脑声明一个int是4字节，即32位

7、，能够表示的数在范围内共个数。所以不难理解，取第一位作正负的标识位（0为非负数、1为负数），剩余的31位恰好能表示的正数。既然如此，取第一位为1，一样能够表示的数，为何还要采用补码这种复杂的表示方式呢？因为这种方法虽然直观，但在计算机内部却不好用的。一是将0表示重复了而忽略了这个数，二为了加减法的方便。如4位内数表以及加减法：十进制二进制十进制二进制00000-8100010001-1111120010-2111030011-3110140100-4110050101-5101160110-610

8、1070111-71001如3-4就能当加法算了00111100_______1111等于-1。谈回lowbit，所以38288=1001010110010000-38288=0110101001110000两者取&与，得10000=16（想想为什么取反加1后能够保持lowbit不变？）需要指出，非负整数都有自己的lowbit（在程序中，对于0的index应要另外处理。）。因为二进制的性质，有的数的lowbit相同，有的数的lowbit相差几个2的数量级，这就给了对index的分级