1 动态区间和
给定数组
- 单点加:将
增加 。 - 区间求和:查询
。
前缀和 可以在
树状数组(Binary Indexed Tree,BIT,也称 Fenwick Tree)保留一些特定区间的和,使修改和查询都只需
2 管辖区间
定义 lowbit(i) 为正整数
int lowbit(int x) {
return x & -x;
}
例如
约定下标从
也就是说,
| 二进制 | 管辖区间 | ||
|---|---|---|---|
| 3 | 0011 | 1 | |
| 6 | 0110 | 2 | |
| 8 | 1000 | 8 | |
| 12 | 1100 | 4 |
下面画出
c[i] 通常不是原数组前缀和;只有
3 前缀查询
设 sum(x) 返回
继续取块,直到右端点变为
long long sum(int x) {
long long res = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
res += c[i];
}
return res;
}
例如查询
每次取走的是当前前缀的一个完整后缀,下一次恰好接着处理左侧剩余部分。因此这些块互不重叠,也没有遗漏。
每次执行 i -= lowbit(i),会清掉二进制最低位的一个
区间和仍由两个前缀相减:
这里 sum(0)=0,因此
4 单点修改
执行
void add(int p, long long v) {
for (int i = p; i <= n; i += lowbit(i)) {
c[i] += v;
}
}
例如
对应区间
4.1 更新路径
这些区间的长度是
设当前下标为
为什么不会跳过中间的块?对
从 lowbit 至少翻倍,所以更新也只需
5 代码实现
下面使用 luogu P3374: 【模板】树状数组 1 的格式:先输入
1 p v:将增加 。 2 l r:查询闭区间的和。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 5;
int n, m;
long long c[maxn];
int lowbit(int x) { return x & -x; }
void add(int p, long long v) {
for (int i = p; i <= n; i += lowbit(i)) c[i] += v;
}
long long sum(int x) {
long long res = 0;
for (int i = x; i > 0; i -= lowbit(i)) res += c[i];
return res;
}
long long range_sum(int l, int r) {
return sum(r) - sum(l - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
long long v;
cin >> v;
add(i, v);
}
while (m--) {
int op;
cin >> op;
if (op == 1) {
int p;
long long v;
cin >> p >> v;
add(p, v);
} else {
int l, r;
cin >> l >> r;
cout << range_sum(l, r) << '\n';
}
}
return 0;
}
全局数组 c 初始为零。逐个调用 add(i, a[i]),使每个块收到其管辖区间内所有元素的贡献,初始化耗时 maxn 预留容量。
5.1 示例
输入:
5 4
2 -1 3 4 5
2 2 4
1 3 -5
2 1 3
2 3 3
输出:
6
-1
-2
第一次查询为
6 边界与接口
- 修改下标必须为正。
lowbit(0)=0,调用add(0,v)会陷入死循环。 - 加法不等于赋值。 若要令
,应先求出旧值,再执行 add(p, v - old);也可以另存原数组维护旧值。 - 和使用
long long。 除答案外,中间块和也必须落在类型范围内。 - 按实际长度更新。 循环上界是
, maxn只决定数组容量,须满足。 - 多组数据重新初始化。 开始新的一组前清空
c[1..n]。
7 练习
完成 luogu P3374: 【模板】树状数组 1 后,手算以下两条路径:
sum(13)会读取哪些c[i]?时, add(5,v)会修改哪些c[i]?
参考结果
查询路径为
修改路径为
8 后续学习
| 分支 | 文章 | 主要变化 |
|---|---|---|
| 区间加 | 区间加与单点查询 | 维护差分,恢复单点值 |
| 区间加 | 区间加与区间求和 | 加入下标权值,恢复区间和 |
| 计数 | 树状数组求逆序对 | 下标改为值的排名,维护频次 |
| 最值 | 前缀最值 | 单调修改,维护前缀最大值 |
| 最值 | 区间最值 | 尾部追加,拆分一般区间 |
| 二维 | 二维树状数组 | 行列分别分块,维护矩形和 |
求和主线依次学习前两篇;其余分支可在理解基础篇后按需阅读,具体前置条件见各篇正文。
9 相关题解
暂无相关题解