一、树状数组
树状数组是一个优美小巧的数据结构，在很多时候可以代替线段树。一句话概括就是，凡是树状数组可以解决的问题，线段树都可以解决，反过来线段树可以解决的问题，树状数组不一定能解决。
树状数组英文名称为Binary Index Tree，直译过来就是二进制索引树，我觉得二进制索引树更能说明其本质。树状数组的本质就是一种通过二进制位来维护一个序列前i和的数据结构。
1、更新元素
比如修改了a[3]，则：
P1 = x = 3, L1 = 0;
P2 = p1+ 2(L1) = 3 + 1 = 4, L2 = 2;
P3 = p2 + 2(L2) = 4 + 4 = 8, L3 = 3;
....
2、子序列求和
比如求sum(6)
p1 = x = 6, L1 = 1; sum += c[6];
p2 = p1 - 2(L1) = 6 - 2 = 4; L2 = 2; sum += c[4];
p3 = p2 - 2(L2) = 4 - 4 = 0, return;
二、树状数组的维护
对于维护的序列A，定义C[i]=A[j+1]+...+A[i]，其中j为i的二进制表示中把最右边的1换成0的值。j的值可以通过lowbit求出，即i-lowbit(i)。
lowbit(a)为2^(a的二进制表示末尾0的个数)。可以用下面式子求出：
lowbit(a)=a&(a ^ (a-1))//或lowbit(a)=a&(~a+1)//或根据补码性质lowbit(a)=a&(-a)
修改方式如下
void modify(int p,int delta) { while (p<=N) { C[p]+=delta; p+=lowbit(p); } }
求前缀和如下
int sum(int p) { int rs=0; while (p) { rs+=C[p]; p-=lowbit(p); } return rs; }
三、示例代码
package ads;/** * * @author loull * 下标index从1开始数 */public class BinaryIndexTree { int[] c; int n; public BinaryIndexTree(int n) { this.n = n; c = new int[n+1]; } int lowbit(int x) { return x & (x ^ (x-1)); } /** * 更新一个元素，初始数组c都是0，所以可以用这个方法初始化c，这时候增加与更新是等价的 * @param p 更新第p个元素，索引从1开始 * @param d 增加的值，不是更新后的值 */ void update(int p, int d) { while (p <= n) { c[p] += d; p += lowbit(p); } } /** * 计算从第一个元素到第p个元素的和 * @param p * @return */ int sum(int p) { int ret = 0; while (p > 0) { ret += c[p]; p -= lowbit(p); } return ret; } public static void main(String[] args) { int[] numbers = {1,2,3,4,5,6,7,8,9}; BinaryIndexTree bit = new BinaryIndexTree(numbers.length); for (int i=0; i
四、C++模板
/**************************************** ** Template of Binary Indexed Tree ** ** @author: Zyzsdy ** ****************************************** Thanks: shu_mj ** ACM Template of Tokyo U ****************************************/templatestruct binaryIndexTree { Type *data; int size_n; binaryIndexTree (int _size) : size_n (_size + 1) { data = new Type[size_n](); } ~binaryIndexTree() { delete [] data; } void add (int _lower, Type _delta) { int pos = _lower + 1; while (pos < size_n) { data[pos] += _delta; pos += pos & -pos; } } Type sum (int _lower, int _upper) { if (_lower > 0) { return sum (0, _upper) - sum (0, _lower); } else { Type result = 0; int pos = _upper; while (pos > 0) { result += data[pos]; pos -= pos & -pos; } return result; } }};typedef binaryIndexTree BIT;
这份树状数组模板支持自动根据数据类型和数据量申请内存，单点更新和区间查询。就算不用模板，这份代码也很容易记忆。。
下面是HDU 1166，典型的树状数组题目，直接套上面的模板就可以解了。。因此不再放出完整代码，只贴上主函数，复制这两份代码再添上头文件即可运行。
int main(int agrc, char *agrv[]) { int T; scanf("%d",&T);for(int i=1;i<=T;i++){ printf("Case %d:n",i); int n; scanf("%d",&n); BIT *ps=new BIT(n); for(int j=0;j updateDelta(j,p); } char buff[80]; while(true){ scanf("%s",buff); if(buff[0]=='E') break; int posi,shuj; switch(buff[0]){ case 'Q': int l,r; scanf("%d%d",&l,&r); printf("%dn",ps->sum(l-1,r)); break; case 'A': scanf("%d%d",&posi,&shuj); ps->updateDelta(posi-1,shuj); break; case 'S': scanf("%d%d",&posi,&shuj); ps->updateDelta(posi-1,-shuj); break; } } delete ps; }}