前缀和数组：
初始化：O(n) 时间复杂度，顺序扫描原数组即可
查询区间和：O(1) 时间复杂度，S[j] – S[i] 即为原数组i到j的区间和
单点修改：O(n) 时间复杂度，需要修改S[i] ~ S[n]所有值
慢，是因为S[i]的值与之前原数组中所有项都有关系
弱化这种关系，即可加快单点修改速度，当然也会丧失部分查询速度。
可这种取舍，是值得的！
lowbit函数
lowbit(i)：代表i这个数字，二进制表示的最后一位1的位权
例如：
- lowbit(8) = (1000)2 = 8
- lowbit(6) = (0110)2 = 2
- lowbit(12) = (1100)2 = 4
- lowbit(7) = (0111)2 = 1
lowbit(x) = x & (-x)
树状数组
改进前缀和：
lowbit(i)：C[i]代表 第i位 的前lowbit(i)项 之和。
例如：
lowbit(10) = 2, C[10] = a[10] + a[9]
lowbit(12) = 4, C[12] = a[12] + a[11] + a[10] + a[9]
前缀和查询：S[i] = S[i – lowbit(i)] + C[i]
例如：
S[7] = S[6] + C[7] = S[4] + C[6] + C[7] = C[4] + C[6] + C[7]
S[12] = S[8] + C[12] = C[8] + C[12]
单点修改：当修改A[j]位置的值的时候，首先需要更新的显然是C[j]的值，可C[j]之后，应该更新哪个值呢？也就是找到C[j]脑袋上面的区间。
要更新的下一个值是：C[i + lowbit(i)]
例如：
更新原数组A[5]的值，那么需要更新C[5],C[6],C[8]这三个点的值
代码实现：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define lowbit(x) (x & (-x))
class FenwickTree {
public :
FenwickTree(int size) : n(size), c(n + 1) {}
// 对原数组进行单点增加 第i位的值增加x
void add(int i, int x) {
while (i <= n) c[i] += x, i += lowbit(i); // 向上更新
return ;
}
// 查询原数组 ind位置的值
int at(int ind) { return query(ind) - query(ind - 1); }
// 查询原数组 x位置前缀和
int query(int x) {
int sum = 0;
while (x) sum += c[x], x -= lowbit(x);
return sum;
}
// 测试输出
void output() {
int len = 0;
for (int i = 1; i <= n; i++) {
len += printf("%5d", i); // 打印坐标位
}
printf("\n");
for (int i = 0; i < len + 6; i++) {
printf("=");
}
printf("\n");
for (int i = 1; i <= n; i++) {
printf("%5d", c[i]); // 打印树状数组
}
printf("\n");
for (int i = 1; i <= n; i++) {
printf("%5d", query(i) - query(i - 1)); // 打印原数组
}
printf("\n\n\n");
return ;
}
private:
int n; // 下标上限
vector<int> c; // 树状数组
};
int main() {
int n;
cin >> n;
FenwickTree tree(n);
for (int i = 1, a; i <= n; i++) {
cin >> a;
tree.add(i, a);
}
tree.output();
int ind, val;
while (cin >> ind >> val) {
cout << "change " << ind << " to " << val << endl;
tree.add(ind, val - tree.at(ind)); // 将原数组ind位置的值 改为val
tree.output();
}
return 0;
}