树状数组 Ｂinary Indexed Tree

本文主要是介绍树状数组 Ｂinary Indexed Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今天学习下一种新的数据结构。
树状数组 英文名字Ｂinary Indexed Tree.
树状数组是为了方便对需要修改的区间进行求和的数据结构。
如果一个数组，需要对其求和，并且当数组元素修改后仍需要对其求和，对这种需要修改，并且修改后需要求和的问题，可以采用树状数组。树状数组采用空间换时间的方式，当需要求和操作时，树状数组并不需要遍历整个数组的操作，而是只需要计算少数几个节点的和，就可以得到修改后所有数组的和。
详细参考。

树状数组有个核心操作是lowbit
lowbit 作用：
设p是一个数的二进制表示中，从右往左数第一个1的位置，或者说是一个数二进制表示中从右往左数遇到1为止，连续0的个数。
比如 4 二进制 100 则p为2,

lowbit 求出的结果是 2^p

ｉnt lowbit(int x){return x&(-x)；
}

那么如何理解这个lowbit函数呢。
首先计算机中负数都是用补码表示的。负数的补码等于,保持符号位不变原码取反并加1。

对于一个数x，从右往左第一个1位置为p，如果 x-1的话，在p以及包含p这个位置所有的数都和x相反。
如果 x XOR (x-1) XOR是异或)的话，则p之前的位都是0

因为x p位是1往后的所有位都是0,
如果 x&(x XOR (x-1)) ,则除了p位是1,所有位都是0
而 -x的补码表示 和 x xor (x-1) 是一样的
所以一般用
x&(-x) 来实现lowbit

关于lowbit 如何理解
详细参考博客：

http://www.cnblogs.com/circlegg/p/7189676.html

树状数组的创建过程。
对于原来数组 a， 树状数组为c
数组下标从1开始
对于下标i

if   i%2==1  // i is odd
c[i]=a[i]
else    // i%2==0 
c[i]=a[i-2^k+1]+...+a[i]// 其中   2^k  等于lowbit(i）  k即是i从右往左数第一位1的位置，或者说0的个数。

对于数组求和操作 求数组前n个数的和

int sum(n){int sum=0;  while(n!=0){sum+=c[n];n-=lowbit(n);}
}

如果更新一个数组a[n] 则c[n]
更新操作

void  change(int i,int x){while(i<=n){c[i]+=x;i+=lowbit(i);}
}

详细参考博客：http://www.cnblogs.com/zhangshu/archive/2011/08/16/2141396.html

这篇关于树状数组 Ｂinary Indexed Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---