0 引言
Leetcode307
这道题给一个可变数组，求从(i)到(j)的元素之和。
一个naive的做法是，每次查询都从(i)累加到(j)：
class NumArray {
public:
NumArray(vector<int>& nums) {
nums_ = nums;
}
void update(int i, int val) {
nums_[i] = val;
}
int sumRange(int i, int j) {
int ans = 0;
for(int l = i;l <= j;++l)
ans += nums_[l];
return ans;
}
private:
vector<int> nums_;
};
这种方法每次更新的复杂度为(O(1))，每次查询的复杂度为(O(n))。
1 树状数组
为了降低查询的复杂度，引入Binary Index Tree(Fenwick Tree)：
BIT其实并不是树，而是维护了一个前缀和数组prefixSums_：
假设有一个数组：
那么我们的tree：
0是dummy node，将结点的二进制表示的最后一个1翻转，就能得到其父结点。
下来填充这棵树：
(1=0+2^0)，存储从下标0开始的前1个数的和：3（0，0）；
(2=0+2^1)，存储从下标0开始的前2个数的和：5（0，1）；
(3=2^1+2^0)，存储从下标2开始的前1个数的和：-1（2，2）；
(4=0+2^2)，存储从下标0开始的前4个数的和：10（0，3）；
(5=2^2+2^0)，存储从下标4开始的前1个数的和：5（4，4）；
(6=2^2+2^1)，存储从下标4开始的前2个数的和：9（4，5）；
(7=2^2+2^1+2^0)，存储从下标6开始的前1个数的和：-3（6，6）；
(8=0+2^3)，存储从下标0开始的前8个数的和：19（0，7）；
(9=2^3+2^0)，存储从下标8开始的前1个数的和：7（8，8）；
(10=2^3+2^1)，存储从下标8开始的前2个数的和：9（8，9）；
(11=2^3+2^1+2^0)，存储从下标10开始的前1个数的和：3（10，10）；
填充后的tree：
接下来就可以根据这棵树来计算prefixSums_：
假如要计算(0-5)的和，从下标6出发，一直加到dummy node，得到prefixSums_[6]=9+10=19；
要计算(0-9)的和，从下标10出发，一直加到dummy node，得到prefixSums_[10]=9+19=28。
以计算(0-9)的和为例，结点10存储的是（8，9）的部分和，结点8存储的是（0，7）的部分和，所以加起来就是(0-9)的和。
2 快速实现
上面求结点的父结点、将下标拆解为二进制去填充树的方式很慢，来看一种稍快的方式。
查询时，我们需要计算从某结点到dummy node的和，这就涉及计算该结点的parent：
假如要求结点7的parent，7的二进制原码为111，-7的补码为001，将原码和补码按位与得001，用原码减去001，得110=6，即7的父结点是6。
更新时，我们需要更新所有包含该结点的部分和结点：
假如更新了结点1，1的二进制原码为001，-1的补码为111，将原码和补码按位与得001，用原码加上001，得010=2，即还要更新结点2，更新了结点2，还要更新结点4......
最后来看下非常简洁的实现：
class BIT{
private:
vector<int> prefixSums_;
static inline int lowbit(int x) {
return x & (-x);
}
public:
BIT(int n) : prefixSums_(n + 1, 0) {}
void update(int i, int delta) {
while(i < prefixSums_.size()) {
prefixSums_[i] += delta;
i += lowbit(i);
}
}
int query(int i) {
int sum = 0;
while(i > 0) {
sum += prefixSums_[i];
i -= lowbit(i);
}
return sum;
}
};
BIT每次查询以及更新的复杂度都是(O(lgn))，适用于动态的更新以及实时查询。
3 Reference
Fenwick Tree or Binary Indexed Tree
花花酱 Fenwick Tree / Binary Indexed Tree SP3