1 问题模型
给定数组
- 区间加:将
内每个数增加 。 - 单点查询:查询当前
。
树状数组基础 支持单点修改。若逐个修改区间内的元素,一次区间加最坏仍需
差分 能把区间加变成两个边界的修改。将它交给树状数组维护,就能处理修改与查询交替出现的情况。
2 维护差分
令
给
增加 ,因为 改变而 不变。 - 对
,相邻两项都增加 ,差值不变。 - 若
, 减少 ,因为 增加而 不变。
因此,只需:
第二处边界超出数组时可以忽略。
例如
树状数组的底层对象变成
同一个 sum(x) 接口,现在求的是差分前缀和,因此结果是原数组单点值
3 操作实现
3.1 初始化
读入数组时,用相邻两项之差初始化树状数组:
long long previous = 0;
for (int i = 1; i <= n; ++i) {
long long value;
cin >> value;
add(i, value - previous);
previous = value;
}
不能直接执行 add(i, value),否则维护的仍是原数组。
3.2 区间加
void range_add(int l, int r, long long v) {
add(l, v);
if (r < n) add(r + 1, -v);
}
第一处修改让所有
3.3 单点查询
long long point_query(int x) {
return sum(x);
}
初始化后,树状数组保存正确的差分。每次区间加恰好修改两个差分边界,继续保持该含义;单点查询再由差分前缀和恢复
4 代码实现
输入输出采用 luogu P3368: 【模板】树状数组 2 的格式:
- 第一行
,第二行为初始数组。 1 l r v:区间加。2 x:查询当前位置的值。
#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;
}
void range_add(int l, int r, long long v) {
add(l, v);
if (r < n) add(r + 1, -v);
}
long long point_query(int x) { return sum(x); }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
long long previous = 0;
for (int i = 1; i <= n; ++i) {
long long value;
cin >> value;
add(i, value - previous);
previous = value;
}
while (m--) {
int op;
cin >> op;
if (op == 1) {
int l, r;
long long v;
cin >> l >> r >> v;
range_add(l, r, v);
} else {
int x;
cin >> x;
cout << point_query(x) << '\n';
}
}
return 0;
}
初始化为 maxn 预留容量。
4.1 示例
输入:
5 5
2 -1 3 4 5
2 2
1 2 4 3
2 2
2 5
2 4
输出:
-1
2
5
7
修改后数组为
5 边界
时正常修改 ,不能使用下标 更新树状数组。 时跳过 ,不需要额外存储这一项差分。 - 区间长度为
、增量为负数时,公式仍然成立。 - 原值、差分、增量和累计值均使用
long long,并保证中间结果在其范围内。 sum(r)-sum(l-1)现在求的是,不能用来求原数组的区间和。
6 练习
完成 luogu P3368: 【模板】树状数组 2,再检查以下操作:
初始数组为
参考结果
最终数组为
下一篇:区间加与区间求和,进一步恢复原数组的前缀和。
7 相关题解
暂无相关题解