「一本通 4.3 例 2」A Simple Problem with Integers

形式化题目

给定长度为 $n$ 的整数序列 $a[1..n]$ ，要求支持 $q$ 次操作：

1 l r x：对所有 $i \in [l, r]$ ，令 $a[i] \gets a[i] + x$ ；
2 l r：求区间和 $\sum_{i=l}^r a[i]$ 。

正解

思路

1. 差分与前缀和的转化

朴素遍历维护区间修改与求和的时间复杂度为 $O(n)$ ，在 $n, q \le 10^6$ 的数据规模下会严重超时。

设差分序列为 $d[i] = a[i] - a[i-1]$ （规定 $a[0] = 0$ ），则由差分性质可知，原数列任意单点值为：

a[i] = \sum_{j=1}^i d[j]

由此，原数列的前缀和 $S_k = \sum_{i=1}^k a[i]$ 可表示为差分数组的双重求和：

S_k = \sum_{i=1}^k \sum_{j=1}^i d[j]

通过统计每个 $d[j]$ 在总和中被累加的次数，可以调换求和次序：

$d[1]$ 在 $a[1], a[2], \dots, a[k]$ 中均出现，共计 $k$ 次；
$d[2]$ 在 $a[2], a[3], \dots, a[k]$ 中均出现，共计 $k - 1$ 次；
一般地， $d[j]$ 在 $a[j], \dots, a[k]$ 中出现，共计 $k - j + 1$ 次。

因此前缀和公式可化简为：

S_k = \sum_{j=1}^k (k - j + 1) d[j] = (k + 1) \sum_{j=1}^k d[j] - \sum_{j=1}^k j \cdot d[j]

2. 双树状数组的维护方案

观察化简后的公式：

$\sum_{j=1}^k d[j]$ 是差分序列 $d[j]$ 的前缀和；
$\sum_{j=1}^k j \cdot d[j]$ 是加权差分序列 $j \cdot d[j]$ 的前缀和。

建立两个树状数组：

树状数组 $T_1$ ：维护序列 $d[i]$ ；
树状数组 $T_2$ ：维护序列 $i \cdot d[i]$ 。

对于两种操作：

区间加 1 l r x：差分序列上仅有两处发生变动： $d[l]$ 增加 $x$ ， $d[r+1]$ 减少 $x$ 。对应加权序列中： $l \cdot d[l]$ 增加 $l \cdot x$ ， $(r+1) \cdot d[r+1]$ 减少 $(r+1) \cdot x$ 。因此在 $T_1$ 的位置 $l$ 加上 $x$ 、位置 $r+1$ 加上 $-x$ ；在 $T_2$ 的位置 $l$ 加上 $l \cdot x$ 、位置 $r+1$ 加上 $-(r+1) \cdot x$ 。
区间查询 2 l r：利用前缀和相减： $\sum_{i=l}^r a[i] = S_r - S_{l-1}$ 。前缀和由公式计算：
$S_k = (k + 1) \cdot \operatorname{query}(T_1, k) - \operatorname{query}(T_2, k)$

单次修改与查询均只需对树状数组进行常数次操作，单次时间复杂度降至 $O(\log n)$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def add(tree1: list[int], tree2: list[int], n: int, pos: int, val: int) -> None:
    """在位置 pos 累加差分增量 val，同时维护 d[i] 与 i*d[i] 的树状数组。"""
    val_weighted = pos * val
    while pos <= n:
        tree1[pos] += val
        tree2[pos] += val_weighted
        pos += pos & -pos


def prefix_sum(tree1: list[int], tree2: list[int], pos: int) -> int:
    """查询前缀 1..pos 的元素和：(pos + 1) * sum(d[i]) - sum(i * d[i])。"""
    sum_d = 0
    sum_id = 0
    i = pos
    while i > 0:
        sum_d += tree1[i]
        sum_id += tree2[i]
        i -= i & -i
    return (pos + 1) * sum_d - sum_id


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    try:
        n_token = next(data)
    except StopIteration:
        return
    n = int(n_token)
    q = int(next(data))

    tree1 = [0] * (n + 1)  # 维护差分序列 d[i]
    tree2 = [0] * (n + 1)  # 维护加权差分序列 i * d[i]

    prev = 0
    for i in range(1, n + 1):
        curr = int(next(data))
        diff = curr - prev
        add(tree1, tree2, n, i, diff)
        prev = curr

    out: list[str] = []
    for _ in range(q):
        op = next(data)
        if op == b'1':
            l = int(next(data))
            r = int(next(data))
            x = int(next(data))
            add(tree1, tree2, n, l, x)
            add(tree1, tree2, n, r + 1, -x)
        else:
            l = int(next(data))
            r = int(next(data))
            ans = prefix_sum(tree1, tree2, r) - prefix_sum(tree1, tree2, l - 1)
            out.append(str(ans))

    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == '__main__':
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:28
 * update_at: 2026-10-05 07:28
 */

// 区间加、区间求和：双树状数组维护差分序列
// 设 d[i] = a[i] - a[i-1]，则前缀和
//   S[k] = sum_{j=1..k} (k-j+1) * d[j] = (k+1) * sum(d[j]) - sum(j * d[j])
// 用 t1 维护 d[i]，t2 维护 i*d[i]，两个操作都只需 O(log n)。

#include <cstdio>

typedef long long ll;

const int MAXN = 1000005;

int n, q;
ll t1[MAXN]; // 维护差分序列 d[i] 的树状数组
ll t2[MAXN]; // 维护加权差分序列 i*d[i] 的树状数组

// 在位置 pos 累加差分增量 val，同时维护 d 与 i*d 两个树状数组
void update(int pos, ll val) {
    if (pos > n) // r+1 可能越界，直接丢弃
        return;
    ll weighted = (ll)pos * val; // 该位置上加权序列的增量
    for (int i = pos; i <= n; i += i & (-i)) {
        t1[i] += val;
        t2[i] += weighted;
    }
}

// 查询前缀 1..pos 的元素和：(pos+1) * sum(d) - sum(i*d)
ll query(int pos) {
    ll sum_d = 0, sum_id = 0;
    for (int i = pos; i > 0; i -= i & (-i)) {
        sum_d += t1[i];
        sum_id += t2[i];
    }
    return (ll)(pos + 1) * sum_d - sum_id;
}

int main() {
    scanf("%d %d", &n, &q);
    // 初始数列按差分拆开建树：a[i]-a[i-1] 加在位置 i
    ll prev = 0;
    for (int i = 1; i <= n; ++i) {
        ll cur;
        scanf("%lld", &cur);
        update(i, cur - prev);
        prev = cur;
    }
    for (int i = 1; i <= q; ++i) {
        int op;
        scanf("%d", &op);
        if (op == 1) { // 区间加：差分上只有 d[l] 与 d[r+1] 两处变化
            int l, r;
            ll x;
            scanf("%d %d %lld", &l, &r, &x);
            update(l, x);
            update(r + 1, -x);
        } else { // 区间求和：两次前缀和相减
            int l, r;
            scanf("%d %d", &l, &r);
            printf("%lld\n", query(r) - query(l - 1));
        }
    }
    return 0;
}

复杂度

时间复杂度：初始建树耗时 $O(n \log n)$ ；每次区间加在两点处修改树状数组，耗时 $O(\log n)$ ；每次区间查询执行两次前缀和查询，耗时 $O(\log n)$ 。总时间复杂度为 $O((n + q) \log n)$ 。
空间复杂度：维护两个长度为 $n + 2$ 的树状数组，辅助空间复杂度为 $O(n)$ 。

图示解析

设序列长度为 $k$ ，前缀和 $S_k$ 是下方所有格子中差分项的和：

text

1
2
3
4
5a[1] = d[1]
a[2] = d[1] + d[2]
a[3] = d[1] + d[2] + d[3]
...
a[k] = d[1] + d[2] + d[3] + ... + d[k]

将每一列的项数统计为一个长方形补全视角：

差分项	出现次数	矩形补全视角 $(k+1) - j$	贡献总和
$d[1]$	$k$	$(k + 1) - 1$	$(k + 1) d[1] - 1 \cdot d[1]$
$d[2]$	$k - 1$	$(k + 1) - 2$	$(k + 1) d[2] - 2 \cdot d[2]$
$d[j]$	$k - j + 1$	$(k + 1) - j$	$(k + 1) d[j] - j \cdot d[j]$
$d[k]$	$1$	$(k + 1) - k$	$(k + 1) d[k] - k \cdot d[k]$

求和即得 $S_k = (k + 1) \sum_{j=1}^k d[j] - \sum_{j=1}^k j \cdot d[j]$ ，二重求和巧妙分解为两个独立前缀和。

总结

区间修改与区间查询通常需要带懒标记的线段树维护，代码量较大。本题通过数学推导，将差分数组的二阶求和转换为“差分前缀和”与“加权差分前缀和”的线性组合，使得两个轻量级的树状数组即可完美替代线段树，既节省了常数开销与代码量，又达到了 $O((n + q) \log n)$ 的最优渐近复杂度。