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

树状数组（二叉索引树）理解与分析 文/龚健飞 说起树状数组，或许很多人会对这个名称或者这个概念感兴趣。但仅仅通过文字上的描述，初学者会比较难地理解到这个数据结构这个算法。我凭自己的认识来阐述一下对这个数据结构的理解，希望给其他初学者一个参考的同时也给自己一个机会更好地认识它。 引言 先用一个问题来引导出树状数组的概念。 给定一个n个元素的的数组，对其进行操作。按照情况，sum(n)表示计算的和，add(x,d)表示让加上d。 显然，对于第一种操作，利用较为简单的前缀和数据可以在O(1)的时间内解决单次问题。但对于第二种操作，前缀和在n足够大的情况下显得无能为力。那么，树状数组能否解决这个问题？要回答这个问题首先得弄清，什么是树状数组。 树状数组 树状数组，顾名思义，即是将所有的数据排列成一棵树的形式，利用分支和源头（更确切地讲，是tree。）掌握数据信息以及进行操作，体现了一点分治的思想。要特别指出，排列成树的依据并不是数据本身，而是数据的索引，即是index。 程序如下： #include iostream using namespace std ; int a[10000]; int c[10000]; int n ; int lowbit(int x){ return x -x ;//求出lowbit } int sum(int x){ int ret = 0 ; while(x 0){ ret += c[x]; x -= lowbit(x) ; } ret += c[0] ; return ret ;//求和函数 } void add(int x , int d){ while(x = n ){ c[x] += d ; x += lowbit(x);//加法操作 } } int main(){ cin n ; for(int i = 0 ; i n ; ++i) cin a[i] ; c[0] = a[0] ; for(int i = 1 ; i n ; ++i){ for(int j = i - lowbit(i) + 1 ; j = i ; ++j) c[i] += a[j] ; //预处理 } int ch ; cout select the operation endl 1 for sum endl 2 for add endl ; while(cin ch){ if(ch == 1 ) { int x ; cin x ; cout sum(x - 1) endl ; } else { int x , d ; cin 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位内数表以及加减法： 十进制 二进制 十进制 二进制 0 0000 -8 1000 1 0001 -1 1111 2 0010 -2 1110 3 0011 -3 1