【數(shù)據(jù)結(jié)構(gòu)】樹狀數(shù)組
講到了線段樹拐辽，那就順便講講樹狀數(shù)組吧。
問題：
- 一個固定大小
n的有限數(shù)組x- action 1 : 可以隨時更新某個節(jié)點
i的元素- action 2 : 可以查詢某個區(qū)間
[i, j]內(nèi)所有元素的和
線段樹
假設(shè)一個長度為 12 的線段樹簇秒，構(gòu)建結(jié)果如下：
構(gòu)建線段樹
在區(qū)間求和問題上，在葉子節(jié)點，顯然劃線部分的值可以由父親節(jié)點 - 左端葉子節(jié)點得到淡诗。
那么覆旱，這部分信息就是冗余的蘸朋，沒有保存的必要。
對于區(qū)間求和問題扣唱，劃線部分是冗余的
同理藕坯，可以推導出所有冗余的部分如下：
同理，所有的冗余部分
那么噪沙，去除冗余部分后的結(jié)果如下：
去除冗余部分
給每一個節(jié)點一個編號炼彪。
我們假設(shè) i 為每個節(jié)點的編號， L[i] 為該節(jié)點包含多少個元素的信息（就是區(qū)間內(nèi)的元素之和）曲聂。
可以得到如下表格霹购。
序號，元素個數(shù)朋腋，二進制表示
再來看看其二進制表示：
每個節(jié)點序號和包含的元素個數(shù)
沒看出規(guī)律齐疙？
我們來分析一下：
| 節(jié)點 | 節(jié)點二進制 | 父節(jié)點 | 父節(jié)點二進制 | 節(jié)點 -> 父節(jié)點 |
|---|---|---|---|---|
| 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 |
以上增加的值對應(yīng)表中的 L[i]。
從上可以看出當前節(jié)點 i 的父節(jié)點是 i+(i的“最低位1”)旭咽，一般稱之為低位技術(shù)：L[i] = i & (-i)
那么 i 節(jié)點的父節(jié)點的序號為：i + L[i]
同樣的規(guī)律贞奋，可以推算出 [1, i] 的值的第一個區(qū)間為 ：i - L[i]
接下來上代碼：
/*
* 假設(shè)樹狀數(shù)組為 T，長度為 n穷绵，序號 [1, ..., n]
*/
// 低位技術(shù)
#define LOWBIT(x) ((x)&(-(x)))
// 獲取區(qū)間 [1, x] 的和
int getSum(int x) {
int ret = 0;
for (int i = x; i > 0; i-=LOWBIT(x)) {
ret += T[i];
}
return ret;
}
// 獲取區(qū)間 [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;
}
}
