【数据结构】树状数组
讲到了线段树，那就顺便讲讲树状数组吧。
问题：
- 一个固定大小
n的有限数组x- action 1 : 可以随时更新某个节点
i的元素- action 2 : 可以查询某个区间
[i, j]内所有元素的和
线段树
假设一个长度为 12 的线段树，构建结果如下：
构建线段树
在区间求和问题上，在叶子节点，显然划线部分的值可以由父亲节点 - 左端叶子节点得到。
那么，这部分信息就是冗余的，没有保存的必要。
对于区间求和问题，划线部分是冗余的
同理，可以推导出所有冗余的部分如下：
同理，所有的冗余部分
那么，去除冗余部分后的结果如下：
去除冗余部分
给每一个节点一个编号。
我们假设 i 为每个节点的编号， L[i] 为该节点包含多少个元素的信息（就是区间内的元素之和）。
可以得到如下表格。
序号，元素个数，二进制表示
再来看看其二进制表示：
每个节点序号和包含的元素个数
没看出规律？
我们来分析一下：
| 节点 | 节点二进制 | 父节点 | 父节点二进制 | 节点 -> 父节点 |
|---|---|---|---|---|
| 1 | 0001 | 2 | 0010 | 0001 + 0001 = 0010 |
| 2 | 0010 | 4 | 0100 | 0010 + 0010 = 0100 |
| 3 | 0011 | 4 | 0100 | 0011 + 0001 = 0100 |
| 4 | 0100 | 8 | 1000 | 0100 + 0100 = 1000 |
| 5 | 0101 | 6 | 0110 | 0101 + 0001 = 0110 |
| 6 | 0110 | 8 | 1000 | 0110 + 0010 = 1000 |
以上增加的值对应表中的 L[i]。
从上可以看出当前节点 i 的父节点是 i+(i的“最低位1”)，一般称之为低位技术：L[i] = i & (-i)
那么 i 节点的父节点的序号为：i + L[i]
同样的规律，可以推算出 [1, i] 的值的第一个区间为 ：i - L[i]
接下来上代码：
/*
* 假设树状数组为 T，长度为 n，序号 [1, ..., n]
*/
// 低位技术
#define LOWBIT(x) ((x)&(-(x)))
// 获取区间 [1, x] 的和
int getSum(int x) {
int ret = 0;
for (int i = x; i > 0; i-=LOWBIT(x)) {
ret += T[i];
}
return ret;
}
// 获取区间 [x, y] 的和
int getSum(int x, int y) {
return getSum(y) - getSum(x - 1);
}
// 更新第 x 点的值
void updateOneNode(int x, int c) {
for (int i = 0; i <= n; i+=LOWBIT(x)) {
T[i] += c;
}
}
