数据结构与算法_树状数组
问题：
一个包含 n 个数的数列 2，7，1，12，5，9，...， 请计算前 i 个数的和值，即前缀和 sum[i] = a[1] + a[2] +...+a[i], i = 1,2,...,n。
如何快速的计算呢？一个一个的加起来吗？
树状数组，可以高效的计算数列前缀和。它的查询（求前缀和）和更新（修改）操作都可以在O(log n)的时间完成。只擅长单点修改，不擅长区间修改。
那么树状数组是怎么巧妙地实现的呢？
1. 树状数组的由来
树状数组引入了分级管理制度，设置一个管理小组，管理小组的每个成员管理一个或多个连续的元素。例如，数列中有9个元素，分别用 a[1] , a[2], ... , a[9] 表示，设置一个管理小组 c[ ] ,如图所示。
（1）查询前缀和
如果想知道 sum[7] 怎么办？
只需要 c[7] 加上左侧所有子树的根即可（把左侧兄弟结点称为前驱），即sum[7] = c[4] +c[6] +c[7]。
（2）修改更新
如果对 a[5] 进行修改，令 a[5] 加上一个数 y，那么需要更新改元素的所有祖先结点。(把祖宗结点称为后继)
2. 树状数组的实现
树状数 组，又称为二进制索引树（Binary indexed trees）,通过“二进制分解” 划分区间。首先要搞清楚：c[i] 保存的是哪些值？
（1）区间长度
如果 i 的二进制表示末尾有 k 个连续的 0, 那么 c[i] 保存的值区间长度为 2^k, 从 a[i] 向前数 2^k 个元素，如图所示。
怎么得到这个区间长度呢？
注：i 取反加一的这个过程就是 -i
在计算机中二进制数采用的是补码表示， -i 的补码刚好是 i 取反加1，因此 （-i）& i 就是区间长度。如果 c[i] 保存的值区间长度用 lowbit(i) 表示，则 lowbit(i) = (-i) & i 。
算法代码：
int lowbit(int i){
return (-i)&i ;
}
(2) 前驱和后继
直接前驱： c[i] 的直接前驱为 c[i-lowbit(i)] , 即 c[i] 左侧紧邻的子树的根；
直接后继： c[i] 的直接后继为 c[i+lowbit(i)], 即 c[i] 的父亲；
前驱： c[i] 的直接前驱，其直接前驱的直接前驱， ... , 即 c[i] 左侧所有的子树的根；
后继: c[i] 的直接后继，其直接后继的直接后继， ... , c[i] 的父亲，其父亲的父亲，即c[i] 的所有祖先。
（3）查询前缀和
求前 i 个元素的前缀和 sum[i] 就等于 c[i] 加上 c[i] 的前缀。例如，sum[7] 就等于 c[7] 加上 c[7] 的前驱， c[7] 的前驱 为 c[6] ，c[4]，因此即 sum[7] = c[7] +c[6] + c[4]。
算法代码：
(4) 修改更新
如果对 a[i] 进行修改，令 a[i] 加上一个数 z, 只需要更新 c[i] 及其后继（祖先），即令这些结点都加上 z 即可，其他结点不需要修改。例如，修改 a[5] , 加上2 ，只需要 c[5]+2, c[5]的后继分别加上2，即 c[6] +2, c[8] +2。
算法代码：
void add(int i, int z) //a[i] 加上 z
{
for(;i<n;i+=lowbit(i))
{
c[i] +=z;
}
}
注意：树状数组下标从1 开始，不能从 0 开始，因为 lowbit(0) = 0，会出现死循环。
（5）查询区间和
如果求区间和值 a[i] + a[i+1] + ... + a[j] ,则求解前 j 个元素的和值减去前 i-1 个元素的和值即可， sum[j] -sum[i-1]。
算法代码：
3. 树状数组的性能分析
树状数组又称为二进制索引树（Binary indexed trees），是通过“二进制分解”划分区间的。树状数组的性能和 n的二进制位数有关，n的二进制位数为 [log n] ， [x] 表示取下限加一。
4. 多维树状数组
前面已经知道一维树状数组修改和查询的时间复杂度均为 O(log n),可以扩展为 m 维树状数组，其时间复杂度为 O(log^m n)。算法只需要加上一层循环即可。
例如，二维数组 a[n][n], 树状数组为 c[ ][ ]，那么其查询和修改的方法如下：
（1）查询前缀和
二维数组的前缀和其实是计算从数组左上角到当前位置（x,y）矩阵的区间和，只需要在一维数组查询前缀和的代码加上一层循环即可。
（2）修改更新
如果对 a[x][y] 进行修改，令 a[x][y] 加上一个数 z, 只需要在一维数组更新的代码加上一层循环即可。
算法代码：
（3）查询区间和值
二维数组查询区间和值，其实是求左上角（x1,y1）到右下角（x2,y2）子矩阵区间和，如图所示。
算法代码：
5.树状数组的局限性
