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

树状数组（二叉索引树）理解与分析文/龚健飞说起树状数组，或许很多人会对这个名称或者这个概念感兴趣。但仅仅通过文字上的描述，初学者会比较难地理解到这个数据结构这个算法。我凭自己的认识来阐述一下对这个数据结构的理解，希望给其他初学者一个参考的同时也给自己一个机会更好地认识它。引言先用一个问题来引导出树状数组的概念。给定一个n个元素的的数组，对其进行操作。按照情况，sum(n)表示计算的和，add(x,d)表示让加上d。显然，对于第一种操作，利用较为简单的前缀和数据可以在O(1)的时间内解决单次问题。但对于第二种操作，前缀和在n足够大的情况下显得无能为力。那么，树状数组能否解决这个问题？要回答这个问题首先得弄清，什么是树状数组。树状数组树状数组，顾名思义，即是将所有的数据排列成一棵树的形式，利用分支和源头（更确切地讲，是tree。）掌握数据信息以及进行操作，体现了一点分治的思想。要特别指出，排列成树的依据并不是数据本身，而是数据的索引，即是index。程序如下：#include using namespace std ;int a10000;int c10000;int n ; int lowbit(int x)return x& -x ;/求出lowbitint sum(int x)int ret = 0 ;while(x 0)ret += cx;x -= lowbit(x) ;ret += c0 ;return ret ;/求和函数void add(int x , int d)while(x n ;for(int i = 0 ; i ai ;c0 = a0 ;for(int i = 1 ; i n ; +i)for(int j = i - lowbit(i) + 1 ; j = i ; +j) ci += aj ; /预处理int ch ;cout select the operation endl 1 for sum endl 2 for add ch)if(ch = 1 ) int x ;cin x ;cout sum(x - 1) x d ;add(x - 1 , d) ; cout select the operation endl 1 for sum endl 2 for add endl ; return 0 ; lowbit(x)某些书上定义lowbit(x)为，x的二进制表达式中最右边的1以及后面的0组成的数（显然，这些lowbit只能是1、2、4、8.）。整个树状数组的精粹就在于lowbit，而这个算法之所以能够这么快也在于每个index的lowbit能够轻易获得，且看程序代码：int lowbit(int x)return x& -x ;/求出lowbit一行代码就能获得lowbit，且只需要一次位运算&。加上位运算是直接基于二进制表达式的，更加接近计算机底层，所以执行起来比普通的加减法还要快。好了，且看lowbit的真正意义。按照上面的定义，38288的二进制是1001010110010000所以lowbit(38288) = 10000（二进制）= 16（十进制）。至于程序中，为什么x& -x能够获得x的lowbit呢？计算机里的负数采用补码表示，即-x 实际上是x按位取反，然后加上1的结果。以下详细理解这句话。补码我们知道，在计算机内部数是由二进制表示的。现在一般的电脑声明一个int是4字节，即32位，能够表示的数在范围内共个数。所以不难理解，取第一位作正负的标识位（0为非负数、1为负数），剩余的31位恰好能表示的正数。既然如此，取第一位为1，一样能够表示的数，为何还要采用补码这种复杂的表示方式呢？因为这种方法虽然直观，但在计算机内部却不好用的。一是将0表示重复了而忽略了这个数，二为了加减法的方便。如4位内数表以及加减法：十进制二进制十进制二进制00000-8100010001-1111120010-2111030011-3110140100-4110050101-5101160110-6101070111-71001如3 - 4 就能当加法算了00111100_1111等于-1。谈回lowbit，所以38288 = 1001010110010000-38288 = 0110101001110000两者取&与，得10000 = 16 （想想为什么取反加1后能够保持lowbit不变？）需要指出，非负整数都有自己的lowbit（在程序中，对于0的index应要另外处理。）。因为二进制的性质，有的数的lowbit相同，有的数的lowbit相差几个2的数量级，这就给了对index的分级划分的依据了。如下图：看到这幅图对数据的划分，然后借鉴前缀和以及分治和tree的思想，会产生什么想法？上下级只相差了下级对应的lowbit，且上级有且只有左右两个分支（所以叫二叉索引树）。如果每一个数点都掌握且只掌握了它以及在它左下分支的数点的数据，即做程序中这样的预处理：c0 = a0 ;for(int i = 1 ; i n ; +i)for(int j = i - lowbit(i) + 1 ; j 0)ret += cx;x -= lowbit(x) ;ret += c0 ;return ret ;/求和函数鉴于lowbit(0) = 0，故while中只有使用x 0才能跳出循环而不是x = 0。由图可知，x -= lowbit(x) 可以令index执行一次就跳到下一个不重叠不遗漏的分支和上（二进制的性质）。add(x , d)之所以舍前缀和而求树状数组的最大原因便是add函数了。void add(int x , int d)while(x = n )cx += d ;x += lowbit(x);/加法操作相比使用前缀和算法每add一次就要循环修改一大批前缀和，由图中和上面分析可知，使用树状数组每add一次只需修改这个index或者这个数点一直往右上的数点的左下分支和直至没有右上分支。这体验了分治的好处，也灵活运用了tree的知识，所以总是管它叫树。时间复杂度时间复杂度掌握了一种算法的生死大权。该程序中，预处理是一个二重循环，时间复杂度较大，是整个算法的软肋。为了使这个程序更快，可以作以下优化：即充分利用之前的左下分支和，组成当前index的左下分支和。优化如下：for(int i = 1 ; i n ; +i)for(int j = i - lowbit(i) + 1 ; j i ; j += lowbit(j)ci += cj;ci += ai ;这样第一重循环时间复杂度为O(n)，第二重因为利用到lowbit，所以复杂度为O(logn)。预处理的总时间复杂度为O(nlogn)。由上面第二重循环