这应该是我碰到过的最复杂的数据结构。。完全摸不着头脑，看了这篇文章，有了一些的认识。
https://www.hackerearth.com/notes/binary-indexed-tree-made-easy-2/
看完这个后再看这篇文章：
http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
segment tree: 线段树
binary index tree: 树状数组
好吧。看完binary index tree 感觉大脑已经无力了。
还记得 range sum 吗？
如果用DP来做，update的时候，复杂度是O(n)
有没有想过为什么复杂度会这么大？
因为啊，每个index，都把之前的 [0, index]都考虑进去了，
所以之前这个区间有任何元素变了，他都得跟着变。
那现在提出一种改良方法：
如果index记录的并不是[0, index]的和，而是另外一种和，这样，当update的时候，有些涉及到的需要更新，有些不涉及的就不需要更新了。这就是
binary index tree的思想。
如果没看懂我再说什么，就自己看我列举出来的第一片文章即可。
比如[1,8]
如果我们按照这样的方式来记录：
[1]: [1]
[2]: [1, 2]
[3]: [3]
[4]: [1,4]
[5]: [5]
[6]: [5,6]
[7]: [7]
[8]: [1,8]
如果index 2的值改变了，我们需要Update哪些？
[1], [2], [4], [8]
看到没？更新的次数从O(n) 变成了O(log n)
...
Fuck, 谁想出来的。。。
那么求和呢？
比如求 [2,5]
那么：
[3,5] = [1,5] - [1,2]
= [1,4] + [5] - [1,2]
= [4] + [5] - [2]
复杂度也变成了: O(log n)
空间复杂度是 O(n)
更多的细节看那篇文章吧。
最后一个问题，给你一个index，如何拆分他？
比如 5，要求 [1,5]
5 = 0101
int ans = 0;
int index = 5;
while (index > 0) {
ans += BIT[index];
index -= (index & -index);
}
如果index 是5的话，0101
0101 -> 0100 ans += BIT[5], index = 4
0100 -> 0000 ans += BIT[4], index = 0
end loop
so:
and = BIT[5] + BIT[4]
= [4] + [5]
sum(5) = [4] + [5]
对了，这篇文章全篇没有考虑 nums[] 到 BIT[] 映射时 +1的问题，自己意会。
如果是更新 nums[]的话,
更新BIT[index];
比如更新 BIT[5]
BIT[0] - BIT[4] 不用任何变化。
BIT[6]
BIT[8]
都需要改变
int index = 5;
int diff = value - nums[index - 1];
while (index < BIT.length) {
BIT[index] += diff;
index += (index & -index);
}
index = 5: 0101
0101
0101 + 0001 = 0110 BIT[6]
0110 + 0010 = 1000 BIT[8]
index & -index 这个比特操作，可以拿到 index最右边第一个是1的位。
比如index =0101
index & -index = 0001
感觉也差不多说了很多了。
自己实现了下：
My code:
public class BinaryIndexTree {
int[] BIT;
int[] nums;
public void initialize(int[] nums) {
this.nums = nums;
BIT = new int[nums.length + 1];
for (int i = 1; i <= nums.length; i++) {
updateBIT(i - 1, nums[i - 1]);
}
}
public int getSum(int qs, int qe) {
if (qs == 0) {
return getSum(qe);
}
else {
return getSum(qe) - getSum(qs - 1);
}
}
private int getSum(int index) {
index = index + 1;
int ans = 0;
while (index != 0) {
ans += BIT[index];
index -= (index & -index);
}
return ans;
}
public void update(int index, int value) {
int diff = value - nums[index];
nums[index] = value;
updateBIT(index, diff);
}
private void updateBIT(int index, int diff) {
index = index + 1;
while (index < BIT.length) {
BIT[index] += diff;
index += (index & -index);
}
}
public static void main(String[] args) {
BinaryIndexTree test = new BinaryIndexTree();
int[] nums = new int[]{1,2,3,4,5};
test.initialize(nums);
int ret = test.getSum(1, 2);
System.out.println(ret);
test.update(2, 4);
ret = test.getSum(1, 2);
System.out.println(ret);
}
}
Anyway, Good luck, Richardo! -- 09/04/2016
