Appearance
问题
数组
- 单点修改:将
加上 ; - 区间查询:查询
的和。
cpp
int a[];
// 单点修改
void set(int id, int v) {
a[id] = v;
}
// 区间查询
int ask(int l, int r) {
int ans = 0;
for(int i = l; i <= r; i ++)
ans += a[i];
return ans;
}
暴力算法( | 树状数组( | |
---|---|---|
单点修改 | ||
区间查询 | ||
构造
在原数组的上方构建树型结构,每个节点表示一段区间和:
; ; ; ;
我们不用立即知道每个
代表的是哪一段的和。
父节点
如何求
将
的父节点为 ; 的父节点为 ; 的父节点为 ;
总结出规律:
的父节点为 lowbit(i) 。
左邻节点
观察同一张图:
的左邻节点为 ; 的左邻节点为 ; 的左邻节点为 ;
总结规律:
的左邻节点为 。
单点修改
将
; ; 。
因此,修改
对于给定的
时间复杂度为
cpp
int lowbit(int x) {
return x & -x;
}
// 将 a[p] 增加 k
void add(int p, int k) {
for(; p <= n; p += lowbit(p)) c[p] += k;
}
区间查询
参考 前缀和 思想:设
自此,问题转换为求任意的
以
; ; 。
因而
查询
时间复杂度为
cpp
// 查询 A[1...p] 的和
int ask(int p) {
int sum = 0;
for (; p; p -= lowbit(p)) sum += c[p];
return sum;
}
// 查询 A[l] ... A[r] 的和
int get(int l, int r) {
return ask(r) - ask(l - 1);
}
模板
cpp
int lowbit(int x) {
return x & -x;
}
void add(int p, int k) {
for (; p <= n; p += lowbit(p)) c[p] += k;
}
int ask(int p) {
int sum = 0;
for (; p; p -= lowbit(p)) sum += c[p];
return sum;
}
int get(int l, int r) {
return ask(r) - ask(l - 1);
}
拓展
一般的树状数组只能实现「单点修改、区间查询」。
通过 差分 技巧,树状数组也可以实现「区间修改、单点查询」。
- 在数组
的差分数组 上建立树状数组,其中 ; - 将
都加上 时, 增加了 , 减少了 。
由于
cpp
// 将 A[l] ... A[r] 加上 v
void seg_add(int l, int r, int v) {
add(l, v);
add(r + 1, -v);
}
// 查询 A[p] 的值
int ask(int p) {
int sum = 0;
for (; p; p -= lowbit(p)) sum += c[p];
return sum;
}
int main() {
/* 输入部分省略 */
for (int i = 1; i <= n; i ++) {
// 在差分数组上建立树状数组
add(i, a[i] - a[i - 1]);
}
}