树状数组解决数组单点更新后快速查询区间和的问题
要解决的问题
数组在不变的情况下，前缀和数组可以用来加速生成i ~ j位置的累加和信息, 假设前缀和数组为preSum，那么i...j的累加和
sum[i...j] = preSum[j] - preSum[i-1]
但是如果数组要单点修改，则以上的情况不适用，树状数组(index tree)就是解决这个问题，时间复杂度可以达到O(logN)。
注：本文所有涉及到的数组操作均从下标1开始计算，下标0位置弃而不用
用辅助数组保存累加信息
申请一个辅助数组help, 大小和原始数组arr一样，保存原始数组的累加信息，但是要基于如下规则来保存。
遍历的位置i如果是奇数，则只管自己这个位置的内容，即：arr[i] = help[i]。
遍历的位置i如果是偶数，则按如下规律：
0010管0001 ~ 0010的累加和，
00100 管 00001 ~ 00100的累加和，
0110 管 0101 ~ 0110的累加和
…
即某个偶数位置接管的区间是：把这个偶数位置二进制最右边的1抹掉后再加1得出的位置一直到这个位置本身。
比如：
1010111000这个位置，把最右边的1抹掉后，值为1010110000,再加1，值为1010110001,所以1010111000这个位置接管的累加和是从1010110001 ~ 1010111000。
通过以上做法生成help数组后，我们可以通过这个help数组快速响应单点更新，并快速求得前缀和。
根据help数组快速计算前缀累加和
按如上流程生成help数组后，如果要计算1..i位置的累加和，则有如下规则：
第一步，提取出i最右侧的1，假设为x，将help[i] + help[i-x]，得出a1
第二步，继续提取i-x最右侧的1，假设为y，将a + help[i- x - y]，得出a2
…
直到i提取完所有最右侧的1，求累加，得到的结果即为1...i上的累加和。
public int sum(int index) {
int ret = 0;
while (index > 0) {
ret += tree[index];
index -= index & -index;
}
return ret;
}
其中index&-index即为index最右侧的1。
i位置的前缀和
如果单点有更新，比如需要在index位置上的值增加一个d，此时需要考虑哪些位置受到了牵连。
单点的二进制最末尾的1加1，依次到数组结尾，都是受到牵连的位置
public void add(int index, int d) {
while (index <= N) {
tree[index] += d;
index += index & -index;
}
}
index += index & -index; 即为受到牵连的位置，所以这些位置都要执行加d的操作。
线段树 VS 树状数组
线段树是树状数组的升级版，树状数组只能做到单点更新后，维持累加和信息的快速更新，线段树可以支持范围更新，但是树状数组可以很方便改成二维或者三维的，对于线段树来说，改成二维的太复杂。
二维树状数组
二维树状数组主要解决：在单点变化时候，快速更新从左上角位置（1,1）累加到(i,j)位置的累加和信息这个问题。
熟悉一维数组后，二维的树状数组比较简单，原先一维数组只需要考虑1...i位置累加和，现在二维除了考虑1...i位置累加和，还要考虑1...j位置的累加和
二维树状数组的sum方法和update方法如下
private int sum(int row, int col) {
int sum = 0;
for (int i = row + 1; i > 0; i -= i & (-i)) {
for (int j = col + 1; j > 0; j -= j & (-j)) {
sum += tree[i][j];
}
}
return sum;
}
public void update(int row, int col, int val) {
if (N == 0 || M == 0) {
return;
}
int add = val - nums[row][col];
nums[row][col] = val;
for (int i = row + 1; i <= N; i += i & (-i)) {
for (int j = col + 1; j <= M; j += j & (-j)) {
tree[i][j] += add;
}
}
}
即在一维的条件下，增加了一个循环。
现在有了二维树状数组，如果要求整个二维平面中，任意[row1,col1]位置到[row2,col2]位置组成的矩形累加和信息，则可以很方便通过二维数状数组计算出来：
public int sumRegion(int row1, int col1, int row2, int col2) {
if (N == 0 || M == 0) {
return 0;
}
return sum(row2, col2) + sum(row1 - 1, col1 - 1) - sum(row1 - 1, col2) - sum(row2, col1 - 1);
}
