第 6 章前缀和与差分：把重复的活提前干完

这一章的两个主角是一对逆运算

前缀和：反复查一段的和 → 一次算好，每次查 O(1)
差分：反复改一段（整段加同一个数）→ 每次改 O(1)，最后一次性还原

它们的关系是：对差分数组求前缀和，就得回原数组。 一个正着用，一个反着用，学会一个就等于学会了两个。

代码加起来不到十行，但它们会出现在后面几乎每一道区间题里 —— 包括第 39 章的线段树，那玩意儿要解决的正是「既要反复查、又要反复改」的场景。

前半场 · 前缀和

1一句话问题

给一个长度 n 的数组，然后有 q 次询问，每次问你 a[l] + a[l+1] + ... + a[r] 是多少。

输入

8 3
3 -1 4 1 -5 9 2 6
2 5
1 8
4 4

输出

-1
19
1

第一行是 n = 8 个数、q = 3 次询问，第二行是数组，之后每行一次询问。输出一行对一次询问。

2 5：问 a[2] + a[3] + a[4] + a[5] = -1 + 4 + 1 + (-5) = -1
1 8：问整个数组的和 = 19
4 4：问 a[4] 一个数 = 1

✓ 这一章开始用 1 基下标

从这一章起，数组一律用 a[1] 到 a[n]，a[0] 空着不用。

不是为了好看 —— 是因为前缀和的公式在 1 基下会变得特别干净，而 0 基会逼着你到处写 +1 -1，然后错一个就全错。竞赛里的区间题几乎都是 1 基，习惯它。

2先用纸笔手算一遍

拿上面那组数据，手算 [2,5]：-1 + 4 + 1 + (-5) = -1。

再算 [1,5]：3 + (-1) + 4 + 1 + (-5) = 2。再算 [1,1]：3。

现在注意一件事：算 [1,5] 的时候，你其实顺带把 [1,1]、[1,2]、[1,3]、[1,4] 都算过了 —— 它们是累加过程中一路经过的中间结果，只是你没记下来。

这就是这一章的全部灵感。先记着这个感觉，第 6 步会用到。

3暴力：每次都从头加一遍

brute.cpp暴力

// 区间求和 —— 暴力：每次询问都从头加一遍
//
// 输入：第一行 n q（数组长度、询问次数）
//       第二行 n 个整数 a[1..n]
//       接下来 q 行，每行两个整数 l r，问 a[l] + a[l+1] + ... + a[r] 是多少
// 输出：q 行，每行一个答案
//
// 这份代码就是题意的逐字翻译：问哪一段，就把那一段加起来。
// **它完全正确**，而且 n、q 小的时候一点问题都没有。
//
// 复杂度 O(nq)：每次询问最坏要加 n 个数，一共 q 次。
// n = q = 100000 时就是一百亿次加法 —— 正文第 4 步会让你亲眼看到它卡死。
//
// 注意这里用的是 1 基下标（a[1] 到 a[n]，a[0] 空着不用）。
// 竞赛里区间题几乎都用 1 基，因为它能让前缀和的公式变得特别干净 ——
// 第 6 步就会看到这一点。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int k = 0; k < q; k++) {
        int l, r;
        cin >> l >> r;

        long long sum = 0;
        for (int i = l; i <= r; i++) sum += a[i];   // ← 慢就慢在这一行

        cout << sum << "\n";
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

逐字翻译，完全正确。n、q 小的时候一点毛病都没有。

4实测：它有多慢

同题对比：每次现加 vs 前缀和

数组长度 n

先跑 20 万（询问次数也是 20 万，每次都问长区间）。跑完改成 30 万试试 —— 暴力是 O(nq)，n 翻倍它慢四倍。

每次现加

前缀和

本机实测（询问次数 = 数组长度，每次询问的区间跨度是半个数组）：

n = q	每次现加 O(nq)	前缀和 O(n+q)
20 000	0.07 秒	0.003 秒
50 000	0.44 秒	0.01 秒
100 000	1.74 秒	0.02 秒
200 000	7.01 秒	0.03 秒

n = q = 10⁵ 是 CSP-J 的常见数据范围，暴力就已经要 1.7 秒了 —— 而大多数题目的时限是 1 秒。这不是「慢一点」，这是 0 分和 100 分的区别。

5慢在哪：同一段被反复加了无数遍

看这两次询问：

问 [1, 5000]     加了 5000 次
问 [1, 5001]     又加了 5001 次

第二次询问里，前 5000 项的和刚刚才算过，但暴力又从头加了一遍。

q 次询问，每次都从头开始，同一批加法被重复了无数遍 —— 这个「重复计算」的味道，是不是和第 2 章的斐波那契很像？

6★ 关键的一步

★ 关键的一步

把「从头到 i」的和全部提前算好，存起来。

定义 s[i] = a[1] + a[2] + ... + a[i]，也就是「前 i 个数的和」。特别地 s[0] = 0。

它可以一遍循环全部算出来，每一项只要一次加法：

s[i] = s[i-1] + a[i];        // 前 i 个 = 前 i-1 个 + 第 i 个

有了它，任何一段的和都是一次减法：

s[r]   = a[1] + ... + a[l-1] + a[l] + ... + a[r]
s[l-1] = a[1] + ... + a[l-1]
------------------------------------------------ 相减
                            a[l] + ... + a[r]     ← 正好是要的

答案 = s[r] - s[l-1]。

预处理 O(n)，每次查询 O(1)。总共 O(n + q)。

⚠ 是 s[l-1]，不是 s[l]

写成 s[r] - s[l] 会少算 a[l] 那一项 —— 前缀和的头号错误。

记不住就现推：s[l] 里已经包含了 a[l]，减掉它就把要的东西减没了。所以要减的是「l 前面那一格」，也就是 s[l-1]。

顺便：这就是 s[0] = 0 存在的理由。 当 l = 1 时，s[l-1] 就是 s[0]。如果没有这一格，你就得写个 if (l == 1) 特判；有了它，公式一视同仁，一个特判都不用。

用一个「零元素」消灭掉一堆边界特判 —— 这是很值得学的一招，后面的差分、树状数组、线段树都在用。

7正解

fast.cpp正解

注意它连原数组都没存 —— 边读边算 s 就够了。

// 区间求和 —— 前缀和
//
// 输入输出和 brute.cpp 完全一样。
//
// 核心就两行：
//     s[i] = s[i-1] + a[i]          预处理，O(n)，只做一次
//     答案 = s[r] - s[l-1]          每次询问 O(1)
//
// s[i] 的含义要说清楚（说不清楚就一定会写错）：
//     **s[i] = a[1] + a[2] + ... + a[i]，也就是「前 i 个数的和」。**
//     特别地 s[0] = 0 —— 前 0 个数的和是 0，这个约定不是随便定的，
//     它让 l = 1 的询问不需要任何特判（s[r] - s[0] = s[r]，天然正确）。
//
// 为什么 s[r] - s[l-1] 就是 [l, r] 的和？
//     s[r]   = a[1] + ... + a[l-1] + a[l] + ... + a[r]
//     s[l-1] = a[1] + ... + a[l-1]
//     一减，前面那一截正好抵消掉，剩下的就是要的那一段。
//
// **注意是 s[l-1] 不是 s[l]。**写成 s[l] 会少算 a[l] 那一项，
// 这是前缀和的头号错误，而且小数据经常看不出来。
//
// 复杂度 O(n + q)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<long long> s(n + 1, 0);        // s[0] = 0
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        s[i] = s[i - 1] + x;              // 边读边算，连原数组都不用存
    }

    for (int k = 0; k < q; k++) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << "\n";  // O(1)
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

trace.cpp过程演示

把预处理和每次「掐头」的过程打印出来，最后还会自己验算一遍。

// 前缀和 —— 把预处理和查询的过程打印出来
//
// 输入：n q / n 个数 / q 行 l r（用小数据，n <= 20）
// 输出：前缀和数组是怎么一格一格长出来的，以及每次查询是怎么「掐头去尾」的
//
// 跑一遍，然后盯住查询那几行：
//   s[r] 是「从头到 r」，s[l-1] 是「从头到 l-1」，
//   一减，多出来的那一截头就被减掉了，剩下的正好是 [l, r]。
//
// 前缀和的全部内容就是这一句话。看懂了就不用背公式。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    if (!(cin >> n >> q)) return 0;
    if (n <= 0 || n > 20) { cout << "这份是用来看过程的，请用 1 <= n <= 20\n"; return 0; }

    vector<long long> a(n + 1, 0), s(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    cout << "原数组   a[i] = ";
    for (int i = 1; i <= n; i++) cout << setw(5) << a[i];
    cout << "\n\n预处理（s[i] = s[i-1] + a[i]，s[0] = 0）：\n";

    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
        cout << "  s[" << setw(2) << i << "] = s[" << setw(2) << (i - 1) << "] + a[" << setw(2) << i << "] = "
             << setw(5) << s[i - 1] << " + " << setw(4) << a[i] << " = " << setw(6) << s[i] << "\n";
    }

    cout << "\n前缀和   s[i] = ";
    for (int i = 1; i <= n; i++) cout << setw(5) << s[i];
    cout << "\n";

    for (int k = 0; k < q; k++) {
        int l, r;
        if (!(cin >> l >> r)) break;
        if (l < 1 || r > n || l > r) { cout << "\n询问 [" << l << ", " << r << "] 越界，跳过\n"; continue; }

        cout << "\n询问 [" << l << ", " << r << "]：\n";
        cout << "  s[" << r << "] = a[1.." << r << "] 的和 = " << s[r] << "\n";
        cout << "  s[" << (l - 1) << "] = a[1.." << (l - 1) << "] 的和 = " << s[l - 1]
             << "　　← 这是多出来的那一截头\n";
        cout << "  相减 = " << s[r] << " - " << s[l - 1] << " = " << (s[r] - s[l - 1]) << "\n";

        cout << "  验算：";
        long long chk = 0;
        for (int i = l; i <= r; i++) { cout << a[i] << (i == r ? "" : " + "); chk += a[i]; }
        cout << " = " << chk << (chk == s[r] - s[l - 1] ? "  ✓\n" : "  ✗ 不一致！\n");
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

8单步看它长出来

前缀和：一次算好，反复查

数组询问 l r

第 1 / 20 步

下标 i

a[i]

-1

-5

s[i]

已答出的询问：（还没有）

s[0] = 0 —— 「前 0 个数的和是 0」。这一格看着没用，但它让 l = 1 的询问不用特判。

先看「前缀和」这一栏：

预处理阶段：s 一格一格往右长，每一格只做一次加法。
查询阶段：绿色的 s[r] 减掉红色的 s[l-1]，中间蓝色那段就是要的答案。
把询问改成 1 8，看红色那一格落在 s[0] 上 —— 那一格是 0，所以什么都没减掉。这就是「零元素消灭特判」的现场。

（「差分」那一栏先别急，第 11 步再回来看。）

9★ 对拍验证

★ 正确的用法

把「前缀和」那一栏换成你自己默写的，再点开始。

对拍器

轮数

生成器专门大量制造 l = 1（要用到 s[0]）和 l = r（单点查询）—— 只靠纯随机的话，这两种边界在小数据里出现得太少，恰恰它们才是出事的地方。

// 区间求和 —— 前缀和
//
// 输入输出和 brute.cpp 完全一样。
//
// 核心就两行：
//     s[i] = s[i-1] + a[i]          预处理，O(n)，只做一次
//     答案 = s[r] - s[l-1]          每次询问 O(1)
//
// s[i] 的含义要说清楚（说不清楚就一定会写错）：
//     **s[i] = a[1] + a[2] + ... + a[i]，也就是「前 i 个数的和」。**
//     特别地 s[0] = 0 —— 前 0 个数的和是 0，这个约定不是随便定的，
//     它让 l = 1 的询问不需要任何特判（s[r] - s[0] = s[r]，天然正确）。
//
// 为什么 s[r] - s[l-1] 就是 [l, r] 的和？
//     s[r]   = a[1] + ... + a[l-1] + a[l] + ... + a[r]
//     s[l-1] = a[1] + ... + a[l-1]
//     一减，前面那一截正好抵消掉，剩下的就是要的那一段。
//
// **注意是 s[l-1] 不是 s[l]。**写成 s[l] 会少算 a[l] 那一项，
// 这是前缀和的头号错误，而且小数据经常看不出来。
//
// 复杂度 O(n + q)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<long long> s(n + 1, 0);        // s[0] = 0
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        s[i] = s[i - 1] + x;              // 边读边算，连原数组都不用存
    }

    for (int k = 0; k < q; k++) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << "\n";  // O(1)
    }
    return 0;
}

点一下即可编辑

值得故意写错的：

s[r] - s[l]（少减一格）→ 每次都少算 a[l]
s[i] = s[i-1] + a[i-1]（下标抄错）→ 整体错位
s 数组只开 n 不开 n+1 → s[n] 越界
s 用 int（数据大时会溢出）→ 这个对拍不一定抓得住！因为生成器造的数据小。真实比赛里 10⁵ 个 10⁹ 就爆 int 了。 前缀和一律开 long long，这是习惯问题，不是判断问题。

后半场 · 差分

10反过来的问题

现在把题目反过来：不查了，改成改。

给一个数组，q 次操作，每次把 a[l..r] 里的每个数都加上 v。所有操作做完之后，输出整个数组。

输入

8 3
3 -1 4 1 -5 9 2 6
2 5 3
1 8 -2
6 8 10

输出

1 0 5 2 -4 17 10 14

第一行是 n = 8 个数、q = 3 次修改，第二行是原数组，之后每行一次「l r v」。

2 5 3：a[2..5] 每个加 3
1 8 -2：整个数组每个减 2
6 8 10：a[6..8] 每个加 10

三次改完之后，把整个数组打印出来。

暴力当然还是逐字翻译（O(nq)）：

diffBrute.cpp暴力

// 区间加 —— 暴力：每次操作都把那一段挨个加一遍
//
// 输入：第一行 n q（数组长度、操作次数）
//       第二行 n 个整数 a[1..n]
//       接下来 q 行，每行三个整数 l r v，表示把 a[l..r] 每个数都加上 v
// 输出：所有操作做完之后的整个数组
//
// 逐字翻译，完全正确，O(nq)。
//
// 请注意这道题和「区间求和」正好是**反过来的**：
//   区间求和：数组不动，反复**查**一段
//   区间加：  不查东西，反复**改**一段，最后才看结果
//
// 有意思的是，这两道相反的题，解法也正好互为逆运算 —— 前缀和与差分。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<long long> a(n + 2, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int k = 0; k < q; k++) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        for (int i = l; i <= r; i++) a[i] += v;      // ← 慢就慢在这一行
    }

    for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

同题对比：每次现改 vs 差分

数组长度 n

20 万个数、20 万次区间加，每次都是长区间。跑完把它改成 30 万。

每次现改

差分

11★ 关键的一步：只记变化量

★ 关键的一步

定义 d[i] = a[i] - a[i-1]（相邻两项的差，约定 a[0] = 0）。

现在把 a[l..r] 整体加 v。想一想哪些「相邻两项的差」变了：

下标:      l-1    l   l+1  ...   r   r+1
原数组:     8     2    5    ...  7    4
每个加 3:   8     5    8    ...  10   4
                 ↑                    ↑
            这里的差变大了 3      这里的差变小了 3
            中间那些差 一 点 没 变

区间内部每一项都加了同一个 v，相邻两项的差当然不变。真正变了的只有两处边界：

d[l]   += v;      // l 和 l-1 之间的差，大了 v
d[r+1] -= v;      // r+1 和 r 之间的差，小了 v

不管区间多长，一次操作只改两个数，O(1)。

全部操作做完之后，对 d 求一遍前缀和，就还原出最终的数组：

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

为什么？因为 d[1]+...+d[i] = (a[1]-a[0]) + (a[2]-a[1]) + ... + (a[i]-a[i-1])，中间全部消掉，只剩 a[i] - a[0] = a[i]。这叫望远镜求和，式子写出来一眼就能看见它们互相抵消。

差分和前缀和是一对逆运算。 这就是为什么这两个东西要放在同一章里讲。

⚠ 数组必须开到 n+2

r 可以等于 n，那 d[r+1] 就是 d[n+1] —— 它在原数组外面。

这一格必须留出来（虽然还原时用不到它），否则就是数组越界。运气好当场崩溃，运气不好静默地改坏了别的变量，然后你查一晚上。

这是差分的头号翻车点，比公式本身更容易出事。

diffFast.cpp正解

// 区间加 —— 差分
//
// 输入输出和 diffBrute.cpp 完全一样。
//
// 差分数组 d 的定义：**d[i] = a[i] - a[i-1]**（相邻两项的差，约定 a[0] = 0）。
// 反过来，对 d 求前缀和就能还原出 a：a[i] = d[1] + d[2] + ... + d[i]。
// **差分和前缀和是一对逆运算**，这是理解这一章的钥匙。
//
// 核心：给 a[l..r] 每个数都加 v，在 d 上只需要动两个位置。
//
//     d[l]   += v      从 l 开始，每一项都比原来大 v（因为 a[l] - a[l-1] 的差变大了 v）
//     d[r+1] -= v      到 r+1 就该恢复原样了，所以把这个差补回来
//
// 为什么只动两个？因为 a[l..r] 内部**整体**加了同一个 v，
// 内部相邻两项的差**一点都没变** —— 变的只有 l 和 l-1 之间、r 和 r+1 之间这两处边界。
//
// 一次操作 O(1)，最后再对 d 求一遍前缀和把 a 还原出来，O(n)。总共 O(n + q)。
//
// ⚠ d 必须开到 n+2：r 可以等于 n，那 d[r+1] 就是 d[n+1]，不开够就是越界。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<long long> a(n + 2, 0), d(n + 2, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];    // 建差分数组

    for (int k = 0; k < q; k++) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        d[l] += v;                                          // O(1)
        d[r + 1] -= v;
    }

    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += d[i];                                        // 对 d 求前缀和 = 还原 a
        cout << cur << " \n"[i == n];
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

diffTrace.cpp过程演示

每次操作只有两个格子变了，中间一格没动 —— 这就是 O(1) 的来历。

// 差分 —— 把「只改两个位置」的过程打印出来
//
// 输入：n q / n 个数 / q 行 l r v（用小数据，n <= 20）
// 输出：每次操作在差分数组上动了哪两个格子，以及最后怎么还原回来
//
// 跑一遍，盯住两件事：
//   1. 不管区间多长，**每次操作都只改两个数**。这就是 O(1) 的来历。
//   2. 中间那些格子一直没被碰过 —— 因为区间内部相邻两项的差根本没变。
//
// 最后那次「求前缀和还原」，请和 fast.cpp 的前缀和对照着看：
// 是同一个循环，一个字都不差。差分和前缀和就是一对逆运算。

#include <bits/stdc++.h>
using namespace std;

void show(const char* name, const vector<long long>& v, int n) {
    cout << name;
    for (int i = 1; i <= n; i++) cout << setw(5) << v[i];
    cout << "\n";
}

int main() {
    int n, q;
    if (!(cin >> n >> q)) return 0;
    if (n <= 0 || n > 20) { cout << "这份是用来看过程的，请用 1 <= n <= 20\n"; return 0; }

    vector<long long> a(n + 2, 0), d(n + 2, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];

    cout << "下标           ";
    for (int i = 1; i <= n; i++) cout << setw(5) << i;
    cout << "\n";
    show("原数组   a[i] =", a, n);
    show("差分     d[i] =", d, n);
    cout << "               （d[i] = a[i] - a[i-1]，约定 a[0] = 0）\n";

    for (int k = 0; k < q; k++) {
        int l, r;
        long long v;
        if (!(cin >> l >> r >> v)) break;
        if (l < 1 || r > n || l > r) { cout << "\n操作 [" << l << ", " << r << "] 越界，跳过\n"; continue; }

        d[l] += v;
        d[r + 1] -= v;
        cout << "\n操作：a[" << l << ".." << r << "] 每个数加 " << v
             << "　→ 只动两个格子：d[" << l << "] += " << v
             << "，d[" << (r + 1) << "] -= " << v;
        if (r + 1 > n) cout << "（d[" << (r + 1) << "] 在数组外面，但必须留着这一格，不然会越界）";
        cout << "\n";
        show("         d[i] =", d, n);
    }

    cout << "\n最后对 d 求前缀和，还原出 a：\n";
    long long cur = 0;
    cout << "         a[i] =";
    for (int i = 1; i <= n; i++) { cur += d[i]; cout << setw(5) << cur; }
    cout << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

现在回到上面那个动画，切到「差分（改区间）」那一栏再看一遍：

每次区间加，只有两格变蓝。中间那些格子从头到尾没被碰过。
最后「还原」那一段，用的就是前缀和那个循环，一个字都没改。

12★ 对拍验证

★ 正确的用法

把「差分」那一栏换成你自己默写的，再点开始。

对拍器

轮数

生成器有一半的概率造出 r = n 的操作 —— 那正是要碰 d[n+1] 的情况。加的值有正有负，避免「只会变大」掩盖错误。

// 区间加 —— 差分
//
// 输入输出和 diffBrute.cpp 完全一样。
//
// 差分数组 d 的定义：**d[i] = a[i] - a[i-1]**（相邻两项的差，约定 a[0] = 0）。
// 反过来，对 d 求前缀和就能还原出 a：a[i] = d[1] + d[2] + ... + d[i]。
// **差分和前缀和是一对逆运算**，这是理解这一章的钥匙。
//
// 核心：给 a[l..r] 每个数都加 v，在 d 上只需要动两个位置。
//
//     d[l]   += v      从 l 开始，每一项都比原来大 v（因为 a[l] - a[l-1] 的差变大了 v）
//     d[r+1] -= v      到 r+1 就该恢复原样了，所以把这个差补回来
//
// 为什么只动两个？因为 a[l..r] 内部**整体**加了同一个 v，
// 内部相邻两项的差**一点都没变** —— 变的只有 l 和 l-1 之间、r 和 r+1 之间这两处边界。
//
// 一次操作 O(1)，最后再对 d 求一遍前缀和把 a 还原出来，O(n)。总共 O(n + q)。
//
// ⚠ d 必须开到 n+2：r 可以等于 n，那 d[r+1] 就是 d[n+1]，不开够就是越界。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<long long> a(n + 2, 0), d(n + 2, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];    // 建差分数组

    for (int k = 0; k < q; k++) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        d[l] += v;                                          // O(1)
        d[r + 1] -= v;
    }

    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += d[i];                                        // 对 d 求前缀和 = 还原 a
        cout << cur << " \n"[i == n];
    }
    return 0;
}

点一下即可编辑

值得故意写错的：

d[r] -= v（少了 +1）→ 区间末尾那一项少加了 v
d[r+1] += v（符号写反）→ 后面所有数全错
数组只开 n+1，遇到 r = n → 越界
忘了先用原数组建 d（直接从全 0 的 d 开始）→ 原数组的值全丢了

再进一步

13二维前缀和：矩形里的和

同样的思路搬到二维：给一个矩阵，反复问某个子矩形里所有数的和。

★ 容斥：多减了的要加回来

s[i][j] = 从左上角 (1,1) 到 (i,j) 这个矩形里所有数的和。

预处理：

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
//        ↑上面那块    ↑左边那块   ↑左上角那块被算了两遍，减掉一次

查询 (x1,y1) 到 (x2,y2)：

s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
//  大矩形     砍掉上面      砍掉左边      左上角被砍了两次，补回来

两个式子是同一个道理。不要背 —— 在纸上画一个 4×4 的格子，把「上面那块」「左边那块」「左上角那块」涂成三种颜色，你会看到左上角被涂了两次。画一次，一辈子不用再背。

sum2d.cpp二维前缀和

样例是 3×4 的矩阵。三个询问分别是：整个矩阵（78）、中间 2×2（34）、单个格子（7）。

// 二维区间求和 —— 二维前缀和
//
// 输入输出和 brute2d.cpp 完全一样。
//
// s[i][j] 的含义：**从 (1,1) 到 (i,j) 这个矩形里所有数的和。**
//
// 预处理（容斥，四项）：
//     s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]
//               ↑上面那块   ↑左边那块   ↑左上角被算了两遍，减掉一次
//
// 查询 (x1,y1) 到 (x2,y2)：
//     s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
//     ↑大矩形     ↑砍掉上面    ↑砍掉左边    ↑左上角被砍了两次，补回来
//
// 这两个式子是同一个道理：**多减了的要加回来。**
// 不要背，在纸上画一个 4×4 的格子，把四块涂上不同颜色，一次就懂了。
// 画一次，一辈子不用再背。
//
// 复杂度 O(nm + q)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    if (!(cin >> n >> m >> q)) return 0;

    // 开到 (n+1) × (m+1)，第 0 行第 0 列全是 0 —— 这样 x1-1 = 0 时不用特判
    vector<vector<long long>> s(n + 1, vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            long long x;
            cin >> x;
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
        }

    for (int k = 0; k < q; k++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << "\n";
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

对拍器

轮数

生成器专门造这三种：整个矩阵、单个格子、贴着第一行或第一列 —— 后者会用到 s[0][*] 和 s[*][0]，是容斥最容易写错的地方。

// 二维区间求和 —— 二维前缀和
//
// 输入输出和 brute2d.cpp 完全一样。
//
// s[i][j] 的含义：**从 (1,1) 到 (i,j) 这个矩形里所有数的和。**
//
// 预处理（容斥，四项）：
//     s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]
//               ↑上面那块   ↑左边那块   ↑左上角被算了两遍，减掉一次
//
// 查询 (x1,y1) 到 (x2,y2)：
//     s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
//     ↑大矩形     ↑砍掉上面    ↑砍掉左边    ↑左上角被砍了两次，补回来
//
// 这两个式子是同一个道理：**多减了的要加回来。**
// 不要背，在纸上画一个 4×4 的格子，把四块涂上不同颜色，一次就懂了。
// 画一次，一辈子不用再背。
//
// 复杂度 O(nm + q)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    if (!(cin >> n >> m >> q)) return 0;

    // 开到 (n+1) × (m+1)，第 0 行第 0 列全是 0 —— 这样 x1-1 = 0 时不用特判
    vector<vector<long long>> s(n + 1, vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            long long x;
            cin >> x;
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
        }

    for (int k = 0; k < q; k++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << "\n";
    }
    return 0;
}

点一下即可编辑

✓ 二维差分也是一样的道理

给一个子矩形整体加 v，在二维差分数组上要动四个角：

d[x1][y1]     += v;
d[x1][y2+1]   -= v;
d[x2+1][y1]   -= v;
d[x2+1][y2+1] += v;

然后对 d 求一次二维前缀和还原。原理和一维完全一致，只是边界从 2 个变成 4 个。

这一章不展开（CSP-J 考到二维差分的概率不高），但你现在已经有能力自己推了 —— 推完拿上面那个二维对拍器验一验，把 brute2d 改成「区间加」版本就行。

14什么时候用不了

⚠ 前缀和的死穴：数组不能变

前缀和的前提是预处理之后数组不再改动。

一旦中间有人改了 a[5]，那么 s[5] 到 s[n] 全部作废，重算要 O(n)。如果题目是「改一次、查一次、改一次、查一次……」交替进行，前缀和就没有优势了。

又要反复改、又要反复查 —— 这正是第 38 章树状数组、第 39 章线段树要解决的问题。到那时你会发现，它们干的事情本质上就是「可以修改的前缀和」。

所以这一章不只是一个技巧，它是后面那两章的引子。判断标准很简单：

场景	用什么
只查不改	前缀和 O(1) 查
只改不查（最后才输出）	差分 O(1) 改
又改又查	树状数组 / 线段树（第 38、39 章）

15自测

下一章预告

第 7 章双指针与滑动窗口，思路上和这一章是亲戚：都是利用「上一步的结果」，避免从头再来一遍。

区别在于前缀和是「提前全算好」，而双指针是「顺着往前挪，边挪边改」。