当许多查询反复询问同一个数组的区间信息时，逐次扫描通常浪费了大量重复计算。前缀和把“多次查询”变成一次预处理，差分则把“多次区间修改”延迟到最后统一还原。

本文选择四道 Codeforces 题，从一维前缀计数开始，走到差分覆盖与排序贪心，最后用双层差分处理“查询作用于操作、操作再作用于数组”的结构。重点是看清信息流向：题目是在反复读取区间，还是反复影响区间？

1. 前缀和与差分是一对逆操作

设原数组为 a，前缀数组 prefix 记录从开头到当前位置的累计值：

1
prefix[i] = a[1] + a[2] + ... + a[i]

那么区间 [l, r] 的和可以用两个前缀相减：

1
sum(l, r) = prefix[r] - prefix[l - 1]

差分数组则记录相邻位置的变化。想给整个区间 [l, r] 增加 value，只需要：

1
2
difference[l]     += value
difference[r + 1] -= value

最后对差分数组求一次前缀和，就能恢复每个位置受到的总影响。

可以用一句话区分：前缀和擅长区间查询，差分擅长区间增减。

2. 313B Ilya and Queries：给“相邻关系”做前缀计数

官方题目：313B Ilya and Queries · 难度 1100 · 官方标签：dp、implementation

题意压缩

给定一个字符串，每次查询区间 [l, r] 中有多少对相邻字符相等。查询很多，但字符串不会改变。

最容易写错的地方，是统计对象并不是字符，而是相邻位置之间的关系。可以构造一个关系数组：

1
equal[i] = (s[i] == s[i - 1])

再对 equal 做前缀计数。这样每个查询只需两个前缀值相减。

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string text;
    cin >> text;

    int length = static_cast<int>(text.size());
    vector<int> prefix(length, 0);

    for (int i = 1; i < length; ++i) {
        prefix[i] = prefix[i - 1] + (text[i] == text[i - 1]);
    }

    int queryCount;
    cin >> queryCount;

    while (queryCount--) {
        int left, right;
        cin >> left >> right;
        --left;
        --right;

        cout << prefix[right] - prefix[left] << '\n';
    }

    return 0;
}

为什么减去 prefix[left]

查询 [left, right] 中的相邻对，左端最早能使用的是 (left, left + 1)。prefix[right] 包含直到 right 为止的相等关系，减掉 prefix[left] 后，恰好移除左端之前和跨入左端的关系。

可以用最小区间检查公式：当 left == right 时，区间只有一个字符，不存在相邻对，答案应为 0。此时代入公式确实得到 prefix[right] - prefix[left] == 0。

复杂度

预处理 O(n)，每次查询 O(1)，总复杂度 O(n + q)，空间复杂度 O(n)。

3. 816B Karen and Coffee：差分统计区间覆盖

官方题目：816B Karen and Coffee · 难度 1400 · 官方标签：binary search、data structures、implementation

题意压缩

有许多推荐温度区间。某个温度被至少 k 个区间覆盖时，称为可接受温度。接下来多次查询 [a, b] 内有多少个可接受整数温度。

这道题有两层预处理：

  1. 用差分统计每个温度被多少个区间覆盖；
  2. 把“覆盖次数至少为 k”转成 0/1，再做前缀和回答查询。
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
#include <iostream>
#include <vector>
using namespace std;

int main() {
    const int maximumTemperature = 200000;

    int intervalCount, requiredCoverage, queryCount;
    cin >> intervalCount >> requiredCoverage >> queryCount;

    vector<int> difference(maximumTemperature + 2, 0);

    for (int i = 0; i < intervalCount; ++i) {
        int left, right;
        cin >> left >> right;
        ++difference[left];
        --difference[right + 1];
    }

    vector<int> acceptablePrefix(maximumTemperature + 1, 0);
    int activeCoverage = 0;

    for (int temperature = 1; temperature <= maximumTemperature; ++temperature) {
        activeCoverage += difference[temperature];
        acceptablePrefix[temperature] = acceptablePrefix[temperature - 1]
            + (activeCoverage >= requiredCoverage);
    }

    while (queryCount--) {
        int left, right;
        cin >> left >> right;
        cout << acceptablePrefix[right] - acceptablePrefix[left - 1] << '\n';
    }

    return 0;
}

为什么是 right + 1

区间是闭区间 [left, right]。在 left 处让覆盖数增加，在 right + 1 处让它恢复，前缀累加后 right 仍然包含在覆盖范围内。

这也是差分题最常见的边界错误。数组需要多开一个位置，确保最大右端点的 right + 1 合法。

复杂度

设温度上界为 M。建立差分是 O(n)，扫描整个值域是 O(M)，每次查询 O(1)，总复杂度 O(n + M + q)。

这种写法依赖值域不大。如果坐标可能达到 10^9，但只出现少量端点，就要考虑坐标压缩或有序事件扫描。

4. 276C Little Girl and Maximum Sum：覆盖次数也是资源

官方题目：276C Little Girl and Maximum Sum · 难度 1500 · 官方标签：data structures、greedy、implementation、sortings

题意压缩

给定一个数组和许多区间，目标是在允许重排数组的前提下，让所有区间和的总和尽可能大。

先交换求和顺序。与其逐个计算区间和，不如问每个位置最终被计算多少次：

1
总贡献 = Σ 数值[i] × 位置覆盖次数[i]

区间覆盖次数可以用差分得到。接下来只剩一个配对问题：最大的数应该放在覆盖次数最多的位置，次大的数放在次多的位置。把两个数组同时排序并逐项相乘即可。

为什么同序排序最优

假设 x <= y，覆盖次数 p <= q。比较两种配对：

1
2
x·p + y·q
x·q + y·p

第一种减去第二种得到 (y - x)(q - p) >= 0，所以大数配大权重不会更差。不断消除逆序配对，就得到同序排序的最优方案。

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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int length, queryCount;
    cin >> length >> queryCount;

    vector<long long> values(length);
    for (long long &value : values) {
        cin >> value;
    }

    vector<long long> difference(length + 1, 0);

    for (int i = 0; i < queryCount; ++i) {
        int left, right;
        cin >> left >> right;
        --left;

        ++difference[left];
        --difference[right];
    }

    vector<long long> frequency(length);
    long long activeCoverage = 0;

    for (int i = 0; i < length; ++i) {
        activeCoverage += difference[i];
        frequency[i] = activeCoverage;
    }

    sort(values.begin(), values.end());
    sort(frequency.begin(), frequency.end());

    long long answer = 0;
    for (int i = 0; i < length; ++i) {
        answer += values[i] * frequency[i];
    }

    cout << answer;
    return 0;
}

代码把输入区间转换成左闭右开形式 [left, right)：左端从 1 下标转成 0 下标后增加，原输入的 right 恰好就是右端后一位，因此直接在 difference[right] 处减少。

为什么必须使用 long long

单个数组值会被许多区间重复计算，乘积和总答案都可能超过 32 位整数范围。即使原数组和覆盖次数分别能放进 int，相乘前也应提升到 64 位。

复杂度

差分与还原为 O(n + q)，排序为 O(n log n)，总复杂度 O(n log n + q)，空间复杂度 O(n)。

5. 295A Greg and Array：先统计操作次数，再更新数组

官方题目：295A Greg and Array · 难度 1400 · 官方标签：data structures、implementation

题意压缩

先给出 m 个区间加法操作，每个操作会给数组的一段区间增加某个值；随后又有 k 个查询，每个查询要求执行编号 [x, y] 内的全部操作。直接展开会同时在“操作区间”和“数组区间”上重复工作。

关键是把两层影响分开：

  1. 在操作编号轴上做差分，算出每个操作总共执行几次；
  2. 将“操作增量 × 执行次数”放到数组轴上的差分；
  3. 最后累加数组差分，得到每个位置的总增量。
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
#include <iostream>
#include <vector>
using namespace std;

struct Operation {
    int left;
    int right;
    long long delta;
};

int main() {
    int length, operationCount, queryCount;
    cin >> length >> operationCount >> queryCount;

    vector<long long> values(length);
    for (long long &value : values) {
        cin >> value;
    }

    vector<Operation> operations(operationCount);
    for (Operation &operation : operations) {
        cin >> operation.left >> operation.right >> operation.delta;
        --operation.left;
        --operation.right;
    }

    vector<long long> operationDifference(operationCount + 1, 0);
    while (queryCount--) {
        int first, last;
        cin >> first >> last;
        --first;
        --last;
        ++operationDifference[first];
        --operationDifference[last + 1];
    }

    vector<long long> valueDifference(length + 1, 0);
    long long executionCount = 0;

    for (int i = 0; i < operationCount; ++i) {
        executionCount += operationDifference[i];
        const long long totalDelta = operations[i].delta * executionCount;
        valueDifference[operations[i].left] += totalDelta;
        valueDifference[operations[i].right + 1] -= totalDelta;
    }

    long long accumulatedDelta = 0;
    for (int i = 0; i < length; ++i) {
        accumulatedDelta += valueDifference[i];
        cout << values[i] + accumulatedDelta << (i + 1 == length ? '\n' : ' ');
    }

    return 0;
}

两个差分数组都多开一个元素，使 right + 1 和 last + 1 可以直接写入。执行次数、单次增量及其乘积都应使用 long long。

每个查询、操作和数组位置都只处理常数次，总复杂度为 O(n + m + k)，空间复杂度为 O(n + m)。这也是离线处理的典型价值：等所有影响收集完，再统一展开。

6. 四道题的方法对照

题目 原始操作 预处理结果 查询/计算阶段 总复杂度
313B 多次读取字符串区间 相邻关系的前缀计数 每次两个前缀相减 O(n + q)
816B 多个区间覆盖 + 多次询问 差分还原覆盖，再做 0/1 前缀 每次两个前缀相减 O(n + M + q)
276C 多个区间决定位置权重 差分还原覆盖频次 排序后同序配对 O(n log n + q)
295A 查询覆盖操作，操作覆盖数组 操作轴与数组轴各做一次差分 两次前缀累加 O(n + m + k)

四题的共同点不是都使用某个模板，而是先把大量区间操作压缩成每个位置的一份摘要。295A 进一步说明，“位置”也可以是操作编号，而不一定是原数组下标。

7. 边界检查清单

  • 前缀数组是否保留了代表“空前缀”的 0；
  • 查询区间是闭区间、开区间，还是左闭右开；
  • 差分数组是否为 right + 1 多开了空间；
  • 统计对象是元素，还是元素之间的关系；
  • 是否需要 long long 保存累计次数、乘积和答案；
  • 值域过大时，是否还能直接扫描每一个坐标；
  • 排序是否会破坏必须保留的原位置关系。
  • 是否存在“查询作用于操作、操作再作用于数据”的第二层影响。

8. 建议的练习顺序

先完成 313B，练习把“相邻关系”转成 0/1 数组；再完成 816B，体会差分与前缀和如何串联；随后完成 276C，把区间频次看成权重并证明排序贪心；最后用 295A 检查自己能否识别两条不同的坐标轴。

如果仍不熟悉固定窗口、双指针和二分，可以先回到 Codeforces 序列优化四题。完整进度会继续维护在 算法练习路径。

官方来源