树状数组

本文参考：树状数组的文章

一、树状数组特点

经常使用树状数组进行维护和查询的操作，如修改某点的值，求某个区间的和。

对于普通数组，修改数组中的值和求和这两个操作在最坏情况下需要O(n)的时间；

对于树状数组，这两个操作的时间均为O(logn)。

图中A为普通数组，C为树状数组。如树状数组第4个元素C4的父节点为C8（4的二进制表示为“0100”，则k=2，4 + 2^2 =8）。

树状数组的存储特点

物理空间上以数组形式连续存储； 逻辑空间上，对于两数组下标x，y（x < y） ，若有 x + 2^k = y（k等于x的二进制表示中末尾0的个数），则称y为父节点，x为子节点。并且，奇数下标一定为叶子结点。

树状数组的结点含义

i = 偶数：Ci = Ci所有子节点的值 + Ai；

i = 奇数：Ci = Ai。

如图中可知： C7 = A7 C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 则我们可知，Ci表示一段普通数组A的连续区间和，其中，右区间边界为i，即Ci对应区间的最后一个元素而为Ai；Ci对应的第一个元素是Ci最左下角的叶子结点，而叶子结点的下标，我们可以通过已知的x + 2^k = y关系式求得。 若i的二进制表示为ABCDE1000，则它的左孩子结点为ABCDE0100，按父子关系逆推，有： ABCDE1000 => ABCDE0100 => ABCDE0010 => ABCDE0001 此时，ABCDE0001为叶子结点。

Ci可表示的A数组的区间的元素个数为2^k，故有以下表达式：

Ci=∑j=i−2k+1iA[j]

二、树状数组的求和

对普通数组A的求和表示为 sum(i)=∑ij=1A[j] 。首先我们同函数lowbit(i)表示 2k 。则有： sum(i)=∑ij=1A[j]=A[1]+A[2]+...+A[i]=A[1]+A[2]+A[i−2k]+A[i−2k+1]+...+A[i]=A[1]+A[2]+A[i−2k]+C[i]=sum(i−2k)+C[i]=sum(i−lowbit(i))+C[i]

int lowbit(int x){ return k&-k; } /*树状数组求和*/ int sum(int x){ int sum = 0; while(x){ sum += C[x]; x -= lowbit(x); } return sum; }

三、树状数组的更新

对树状数组的更新，在树状数组C上进行。因为Ai的改变会影响Ci及其父节点。

/*树状数组的更新*/ void add(int x, int num){ while(k < n){ C[x] += num; x += lowbit(x); } }