区间加与区间求和

1 从单点到区间

上一篇 区间加与单点查询 用差分前缀和恢复一个位置的值:

ai=∑j=1idj. a_i=\sum_{j=1}^{i}d_j.

现在要求在区间加之后,查询原数组 [l,r][l,r] 的和。逐点恢复再相加,最坏需要 O(nlog⁡n)O(n\log n)。需要直接计算原数组前缀和:

P(x)=∑i=1xai. P(x)=\sum_{i=1}^{x}a_i.

得到 PP 后,区间和仍是 P(r)−P(l−1)P(r)-P(l-1)。

2 差分的贡献

将每个 aia_i 展开为差分前缀:

a1=d1,a2=d1+d2,a3=d1+d2+d3, ⋮ax=d1+d2+⋯+dx. \begin{aligned} a_1&=d_1,\\ a_2&=d_1+d_2,\\ a_3&=d_1+d_2+d_3,\\ &\ \vdots\\ a_x&=d_1+d_2+\cdots+d_x. \end{aligned}

把这些行相加,就是 P(x)P(x)。从列来看,djd_j 出现在第 jj 行到第 xx 行,共 x−j+1x-j+1 次。

x 等于 4 时,差分 d1、d2、d3、d4 在原数组前缀和中分别出现 4、3、2、1 次

因此:

P(x)=∑j=1x(x−j+1)dj=(x+1)∑j=1xdj−∑j=1xj dj. \begin{aligned} P(x) &=\sum_{j=1}^{x}(x-j+1)d_j\\ &=(x+1)\sum_{j=1}^{x}d_j-\sum_{j=1}^{x}j\,d_j. \end{aligned}

关键是把查询位置 xx 与差分下标 jj 分开。对于一次给定的查询,x+1x+1 是常数;剩下只需要维护两种前缀和。

3 两棵树状数组

数组 维护的底层值 前缀查询结果
c1 djd_j ∑j=1xdj\sum_{j=1}^{x}d_j
c2 j djj\,d_j ∑j=1xj dj\sum_{j=1}^{x}j\,d_j

这两棵树的块结构完全相同,只有加入的权值不同。

3.1 差分修改

对差分位置 pp 增加 vv,同时执行:

add(c1, p, v);
add(c2, p, p * v); // v 为 long long,乘法按 long long 计算

因为 pp 固定,p dpp\,d_p 的增量恰好为 p vp\,v。将这一操作封装成 change(p,v)。

原数组区间 [l,r][l,r] 加 vv,就对应:

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) 是差分前缀和,即单点值 axa_x;prefix_sum(x) 才是原数组前缀和。二者需要区分。

3.3 手算

原数组 [1,2,3,4,5][1,2,3,4,5],给 [2,4][2,4] 加 1010 后:

a=[1,12,13,14,5],d=[1,11,1,1,−9]. a=[1,12,13,14,5],\qquad d=[1,11,1,1,-9].

查询前缀 P(3)P(3),两棵树分别返回:

∑j=13dj=13,∑j=13j dj=1+22+3=26. \sum_{j=1}^{3}d_j=13,\qquad \sum_{j=1}^{3}j\,d_j=1+22+3=26.

所以 P(3)=4×13−26=26P(3)=4\times13-26=26,与 1+12+131+12+13 相同。

4 正确性

初始化时,将每个差分 djd_j 及其加权值 j djj\,d_j 分别加入两棵树。区间加只改变两个差分边界,而 change 同步维护两种增量,所以两棵树始终表示当前差分。

前缀查询按贡献次数恒等式恢复 P(x)P(x),再由两个前缀相减得到区间和。每次修改与每次查询都保持了对应的数组含义。

5 代码实现

采用 luogu P3372: 【模板】线段树 1 的输入输出格式。这道题的“区间加与区间求和”也可以用双树状数组实现。

  • 第一行 n,mn,m,第二行为初始数组。
  • 1 l r v:将闭区间 [l,r][l,r] 内每个数增加 vv。
  • 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;
}

两棵树每次只进行常数次修改或查询,所以单次操作仍为 O(log⁡n)O(\log n);初始化为 O(nlog⁡n)O(n\log n),有效存储为 O(n)O(n)。数组上限由 maxn 指定,须满足 n<maxnn<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。即使最终区间和较小,j djj\,d_j 和 (x+1)∑dj(x+1)\sum d_j 也可能较大,须核对中间量范围。

有的写法维护 (j−1)dj(j-1)d_j,公式相应为 x∑dj−∑(j−1)djx\sum d_j-\sum(j-1)d_j。两套公式等价,但树中维护的权值必须与查询公式一致,不能混用。

7 练习

完成 luogu P3372: 【模板】线段树 1。再设原数组全为零,对 [2,4][2,4] 加 33,分别计算 P(1),P(3),P(5)P(1),P(3),P(5),检查右边界抵消是否生效。

参考结果

差分的非零项为 d2=3,d5=−3d_2=3,d_5=-3。因此:

P(1)=0,P(3)=2×3=6,P(5)=3×3=9. P(1)=0,\qquad P(3)=2\times3=6,\qquad P(5)=3\times3=9.

当 x≥5x\ge5 时,区间增量对前缀和的贡献保持为 99,不会继续增长。

8 相关题解

暂无相关题解