维基百科： 树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。
其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。
算法精妙之处：
-
lowbit()函数：返回二进制输入值最低位的1，如：11100==>100
int lowbit(int x) { return x & -x;}
利用上面的函数我们就可以构建出树状数组：
例如：值得注意的是以1开始
| i | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| lowbit(i) | 1 | 2 | 1 | 4 | 1 | 2 |
| next(i) | 2 | 4 | 4 | 8 | 6 | 8 |
输入：
input[i] = { 8, 9, 35, 5, 8, 47 }
- input的树状数组：R为边界
- 构建树状数组：
构建树状数组
- 更新数组update(i, delta)：
sum[i] += delta
示例update(2, 3)：关注第2个和第4个结点的变化
update
- 查询前缀和query(i)：查询第 i 个的前缀和
示例query(6)：即sum[4] + sum[5] + sum[6]
Query
时间复杂度：构建：O（N）、更新和查询：O（logN）
空间复杂度：O（N）
Talk is cheap. Show me the code!
#include <bits/stdc++.h>
using namespace std;
class FenwickTree {
public:
FenwickTree(int n) : sum(n + 1, 0) {}
void update(int i, int delta) {
while (i < sum.size()) {
sum[i] += delta;
i += lowbit(i);
}
}
int query(int i) {
int s = 0;
while (i < sum.size()) {
s += sum[i];
i -= lowbit(i);
}
return s;
}
private:
vector<int> sum;
static inline int lowbit(int x) { return x & -x; }
};
试着挑战一下leetcode上面的题目吧 ；）
小和问题：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/
区间和个数：https://leetcode-cn.com/problems/count-of-range-sum/
