1 从单点到区间
上一篇 区间加与单点查询 用差分前缀和恢复一个位置的值:
现在要求在区间加之后,查询原数组
得到
2 差分的贡献
将每个
把这些行相加,就是
因此:
关键是把查询位置
3 两棵树状数组
| 数组 | 维护的底层值 | 前缀查询结果 |
|---|---|---|
c1 |
||
c2 |
这两棵树的块结构完全相同,只有加入的权值不同。
3.1 差分修改
对差分位置
add(c1, p, v);
add(c2, p, p * v); // v 为 long long,乘法按 long long 计算
因为 change(p,v)。
原数组区间
change(l, v);
if (r < n) change(r + 1, -v);
3.2 前缀与区间
long long prefix_sum(int x) {
return (x + 1LL) * sum(c1, x) - sum(c2, x);
}
long long range_sum(int l, int r) {
return prefix_sum(r) - prefix_sum(l - 1);
}
sum(c1,x) 是差分前缀和,即单点值 prefix_sum(x) 才是原数组前缀和。二者需要区分。
3.3 手算
原数组
查询前缀
所以
4 正确性
初始化时,将每个差分 change 同步维护两种增量,所以两棵树始终表示当前差分。
前缀查询按贡献次数恒等式恢复
5 代码实现
采用 luogu P3372: 【模板】线段树 1 的输入输出格式。这道题的“区间加与区间求和”也可以用双树状数组实现。
- 第一行
,第二行为初始数组。 1 l r v:将闭区间内每个数增加 。 2 l r:查询该闭区间的和。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 5;
int n, m;
long long c1[maxn], c2[maxn];
int lowbit(int x) { return x & -x; }
void add(long long c[], int p, long long v) {
for (int i = p; i <= n; i += lowbit(i)) c[i] += v;
}
long long sum(const long long c[], int x) {
long long res = 0;
for (int i = x; i > 0; i -= lowbit(i)) res += c[i];
return res;
}
void change(int p, long long v) {
add(c1, p, v);
add(c2, p, p * v);
}
void range_add(int l, int r, long long v) {
change(l, v);
if (r < n) change(r + 1, -v);
}
long long prefix_sum(int x) {
return (x + 1LL) * sum(c1, x) - sum(c2, x);
}
long long range_sum(int l, int r) {
return prefix_sum(r) - prefix_sum(l - 1);
}
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;
change(i, value - previous);
previous = value;
}
while (m--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
long long v;
cin >> v;
range_add(l, r, v);
} else {
cout << range_sum(l, r) << '\n';
}
}
return 0;
}
两棵树每次只进行常数次修改或查询,所以单次操作仍为 maxn 指定,须满足
5.1 示例
输入:
5 4
1 2 3 4 5
2 1 5
1 2 4 10
2 1 3
2 4 5
输出:
15
26
19
6 适用边界
这里的区间修改必须是加法增量。区间赋值、区间乘法不能直接套用这两棵树。
所有存储、增量与乘法使用 long long。即使最终区间和较小,
有的写法维护
7 练习
完成 luogu P3372: 【模板】线段树 1。再设原数组全为零,对
参考结果
差分的非零项为
当
8 相关题解
暂无相关题解