一颗爱编程的心
为了对树状数组有个形象的认识，我们先看下面这张图。如图所示，红色矩形表示的数组C就是树状数组。这里，C[i]表示A[i-2k +1]到A[i]的和，而k则是i在二进制时末尾 0 的个数，或者说是i用 2 的幂方和表示时的最小指数。当然，利用位运算，我们可以直接计算出 2k =i and (i xor (i-1)) 或i and (-i)同时，我们也不难发现，这个 k 就是该节点在树中的高度，因而这个树的高度不会超过logn。所以,当我们修改 A[i]的值时，可以从 C[i]往根节点一路上溯，调整这条路上的所有C 即可，这个操作的复杂度在最坏情况下就是树的高度即 O(logn)。另外，对于求数列的前 n 项和，只需找到 n 以前的所有最大子树，把其根节点的 C 加起来即可。不难发现，这些子树的数目是 n 在二进制时 1 的个数，或者说是把 n 展开成 2 的幂方和时的项数,因此，求和操作的复杂度也是 O(logn)。树状数组C，其中C[i]=a[i-2k+1]+……+a[i](k为i在二进制形式下末尾 0 的个数)。由c数组的定义可以得出：c[1]=a[1]c[2]=a[1]+a[2]=c[1]+a[2]c[3]=a[3]c[4]=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4]c[5]=a[5]c[6]=a[5]+a[6]=c[5]+a[6]1c[7]=a[7]c[8]= a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]=c[4]+c[6]+c[7]+a[8]………………c[16]=a[1]+a[2]+………………………+a[16]=c[8]+c[12]+c[14]+c[15]+a[16]c 数组的结构对应一棵树，因此称之为树状数组。
给出一些树状数组的实现代码，希望读者能够仔细体会其中的细节。
1.求最小幂 2^k建立树状数组c、更新元素值、子序列求和，都与 2^k有关。所以令lowbit(i)=2^k。（其中k为i在二进制下未尾 0 的个数）C++语言：int Lowbit(int t){return t & ( t ^ ( t - 1 ) );} //endPascal 语言：Function lowbit(x:longint):longint;var t:longint;begint:=x and (x (xor(x-1));exit(t); //相当于 lowbit:=t;end;其实lowbit(i)=2k=i and (i xor (i-1))
2.对某个元素进行加法操作： 将 a[p]的值加上一个值 x(x 可正可负)C++语言：int plus(int p , int x){while(p <= maxn)//maxn 为给定范围的上限{c[p] += x;p += Lowbit(p);}}Pascal 语言：procedure plus(p,x:longint);beginwhile p<=maxn do//maxn 为给定范围的上限beginc[p]:=c[p]+x;p:=p+lowbit(p)end;end;
3.求前 p 项和： 统计 a[1]...a[p]的和C++语言：int sum(int p){int sum = 0;while(p > 0){sum+ = c[p];p- = Lowbit(p);}return sum;}Pascal 语言：Function sum(p:longint):longint;vars:longint;begins:=0;while p>0 dobegins:=s+c[p];p:=p-lowbit(p);end;exit(s); //相当于 sum:=s;end;
4.统计 a[x]..a[y]的值调用以上的 sum 操作：sum[y]-sum[x-1]一维的树状数组的每个操作的复杂度都是 O(logn)的，非常高效。它可以扩充为 n 维，这样每个操作的复杂度就变成了 O((logn)^n)，在 n 不大的时候可以接受。扩充的方法就是将原来改变和查询的函数中的一个循环改成嵌套的 n 个循环在 n 维的 c 数组中操作。要注意树状数组能处理的是下标为 1..n 的数组，绝对不能出现下标为 0 的情况。因为lowbit(0)=0，这样会陷入死循环。