信息学竞赛 C++ 教材

Appearance

第 35 章 预制计算——前缀和与差分 ​

🏗️ 前情回顾：上一章你用双指针把许多 O(n²) 的问题压到了 O(n)。但还有一类问题双指针也解决不了——"多次查询区间和"。比如给你一个数组，要回答 10 万次"区间 [l, r] 的元素和是多少"，每次都用循环累加？那还是 O(nq)，q = 10⁵ 时必超时。这一章教你一个神奇的技巧：预处理一次，查询一步到位！

🎯 本章目标 ​

学完这一章，你能：

  • 理解前缀和的核心思想：用空间换时间，预处理 O(n)，查询 O(1)
  • 熟练构建一维前缀和数组并进行区间和查询
  • 掌握差分数组：区间修改 O(1)，单点还原 O(n)
  • 扩展到二维前缀和（子矩阵和查询）
  • 扩展到二维差分（子矩阵修改）
  • 解决最大子段和（前缀和视角）、领地选择、海底高铁等经典问题

📖 故事引入 ​

期末考试后，老师要统计全班 n 个人的总分。最"笨"的办法：每问一个-"第 5 名到第 20 名的总分是多少？"就把第 5 名到第 20 名的成绩加一遍。全班 50 人还好，但如果是一个年级 2000 人，年级组长问 100 次呢？每次都要现场加一遍，效率极低。

聪明人怎么做？提前算好一个表：第 1 名到第 i 名的累计总分是 pre[i]。那么"第 l 名到第 r 名的总分"就是 pre[r] - pre[l-1]，一次减法搞定，不管 l 和 r 离多远！

这就是前缀和的思想——"先算后用"。就像你去超市购物，收银员不会每件商品都加一遍你买的 + 前一位的 + 再前一位的，而是直接从扫描枪里读取累计金额。因为"累计金额"就是实时更新的前缀和。

🧱 知识讲解 ​

35.1 前缀和：构建与查询 ​

定义：对于数组 a[1..n]，它的前缀和数组 pre[i] 定义为前 i 个元素的和：

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

其中 pre[0] = 0（空前缀和，方便后续减法）。

📦 类比：前缀和就像里程表。你从第 0 公里出发，开到第 5 公里时里程表显示 5km，开到第 20 公里时显示 20km。那么第 5 公里到第 20 公里的路程 = 20 - 5 = 15km——这就是 pre[20] - pre[4]。

构建代码（一维）：

cpp
int a[100005], pre[100005];
int n;

// 构建前缀和
pre[0] = 0;
for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] + a[i];
}

// 查询区间 [l, r] 的和
int query(int l, int r) {
    return pre[r] - pre[l - 1];
}

复杂度：预处理 O(n)，每次查询 O(1)。如果查询 q 次，总复杂度 O(n + q)，远优于暴力的 O(nq)。

35.2 差分数组：区间修改神器 ​

前缀和的"逆运算"就是差分。前缀和让你快速求区间和，差分让你快速做区间修改。

定义：对于原数组 a[1..n]，差分数组 d[i] 定义为：

d[1] = a[1]
d[i] = a[i] - a[i-1]   (i > 1)

反过来，a[i] = d[1] + d[2] + ... + d[i]，即 a 是 d 的前缀和。

差分的核心用途：要对区间 [l, r] 每个元素都加 val：

操作代码含义
d[l] += val从 l 开始，"增量"生效
d[r+1] -= val从 r+1 开始，"增量"取消

然后对 d 做一次前缀和就能还原修改后的 a 数组。

cpp
int d[100005] = {0};

// 构建差分
d[1] = a[1];
for (int i = 2; i <= n; i++)
    d[i] = a[i] - a[i - 1];

// 区间 [l, r] 全部 +val
void add(int l, int r, int val) {
    d[l] += val;
    d[r + 1] -= val;
}

// 还原数组
for (int i = 1; i <= n; i++)
    a[i] = a[i - 1] + d[i];

📦 类比：差分就像记账。你每天的存款余额是 a[i]，差分 d[i] 是"今天存了多少钱"。当你把 3 月 1 日到 3 月 10 日的余额各加 100（d[3/1] += 100, d[3/11] -= 100），重新"轧账"一次（前缀和），就得到了更新后的全部余额。

复杂度：每次区间修改 O(1)，最后还原 O(n)。如果 m 次修改 + q 次单点查询，总复杂度 O(m + n + q)，远优于暴力的 O(mn + q)。

海底高铁（差分经典题）：

某城市有 n 个地铁站，小明要从站 1 出发依次经过站 p₁, p₂, ..., pₙ（每次从一站坐到相邻站）。每两个相邻站之间有"纸质票"和"IC 卡"两种方式：纸质票每次固定价格，IC 卡需要买卡费但之后每次便宜。问小明的最小总花费。

思路：先统计每条相邻路段被经过的次数（用差分）。比如从 3 号站坐到 5 号站，意味着经过 3→4 和 4→5 两段。对每段"3→4"和"4→5"各 +1 次。用差分统计所有路段的经过次数，然后对每条路段，比较"全用纸质票"和"买 IC 卡 + IC 卡单次"的总价，取最小值。

cpp
long long cnt[100005] = {0};  // cnt[i] = 路段 i→i+1 经过次数

for (int k = 1; k < m; k++) {
    int from = p[k], to = p[k+1];
    if (from > to) swap(from, to);
    cnt[from]++;      // 差分起点
    cnt[to]--;        // 差分终点
}
// 前缀和还原
for (int i = 1; i < n; i++)
    cnt[i] += cnt[i-1];

// 计算最少花费
long long ans = 0;
for (int i = 1; i < n; i++) {
    ans += min(cnt[i] * A[i], C[i] + cnt[i] * B[i]);
    // A=纸质票价格, B=IC卡单次价, C=IC卡办卡费
}

35.3 二维前缀和：子矩阵和 ​

从一维推广到二维，前缀和就是矩阵的面积和。

定义：pre[i][j] = 以 (1,1) 为左上角、(i,j) 为右下角的子矩阵元素之和。

递推公式（容斥原理）：

pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]

📦 类比：你有一块矩形农田，pre[i][j] 是(1,1)到(i,j)这块地的总产量。想知道中间任意子矩形的产量：(x1,y1)→(x2,y2) = 大面积 - 左边条 - 上边条 + 重叠角（加回来因为被减了两次）。

子矩阵查询公式：

sum(x1, y1, x2, y2) =
    pre[x2][y2]
    - pre[x1-1][y2]
    - pre[x2][y1-1]
    + pre[x1-1][y1-1]
cpp
int pre[1005][1005];

// 构建二维前缀和
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        pre[i][j] = pre[i-1][j] + pre[i][j-1]
                    - pre[i-1][j-1] + a[i][j];

// 查询子矩阵和
int query(int x1, int y1, int x2, int y2) {
    return pre[x2][y2] - pre[x1-1][y2]
           - pre[x2][y1-1] + pre[x1-1][y1-1];
}

⚠️ 容斥原理示意图：四个区域加减——大面积减两条，再加回重叠 —— 容易记错，建议画图辅助记忆。

35.4 二维差分：子矩阵批量修改 ​

和一维差分一样，二维差分用来做子矩阵的批量增减。

构建：d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

子矩阵 (x1,y1)→(x2,y2) 全部加 val：

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

四条指令，O(1) 完成子矩阵修改。还原时做二维前缀和：

cpp
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        a[i][j] = a[i-1][j] + a[i][j-1]
                  - a[i-1][j-1] + d[i][j];

领地选择（二维前缀和经典题）：

在 n×m 的矩阵中，找一个 c×c 的子正方形，使得子矩形的元素和最大。输出最大值和子正方形左上角坐标。

枚举所有可能的子正方形左上角，用二维前缀和 O(1) 查询该 c×c 区域的和，遍历一次即可。复杂度 O(nm)，暴力累加每个 c×c 是 O(nmc²)，差距巨大。

35.5 最大子段和：前缀和视角 ​

题目：给定一个长度为 n 的整数数组（可能有负数），求最大连续子段和。

你已经知道 Kadane 算法的 O(n) 递推法。这里从前缀和的角度来看：

核心观察：子段和 = pre[r] - pre[l-1]。要最大化这个值，对于每个 r，需要找前面最小的 pre[l-1]。

cpp
int maxSubarraySum(int a[], int n) {
    int pre = 0, minPre = 0, ans = a[1];
    for (int i = 1; i <= n; i++) {
        pre += a[i];
        ans = max(ans, pre - minPre);  // 以 i 结尾的最大子段和
        minPre = min(minPre, pre);     // 维护最小前缀和
    }
    return ans;
}

这个写法只需要 O(1) 额外空间，一行行扫描即可——与 Kadane 等价，但从前缀和的角度理解更自然。

✋ 动手试试 ​

试试 1：写一维前缀和程序，输入数组和 q 个区间查询，每个查询 O(1) 输出答案。

试试 2：写一维差分程序，输入数组，进行 m 次区间加法，最后输出结果数组。

试试 3：在 n×m 矩阵中，用二维前缀和实现 q 次子矩阵查询。

⚠️ 容易犯的错 ​

错 1：前缀和查询时下标偏移 ​

❌ pre[r] - pre[l] ——丢失了 a[l]，结果少了一个元素。

✅ pre[r] - pre[l-1]。画图验证：区间 [3,5] 应该包含 a[3]、a[4]、a[5] 三个元素。

错 2：差分还原时忘记累加 ​

❌ 差分数组 d 做完操作后直接输出 d[i] 当结果。

✅ 对 d 做一次前缀和才能还原出修改后的数组 a。

错 3：二维前缀和公式记反 ​

❌ pre[i][j] = pre[i-1][j] + pre[i][j-1] + pre[i-1][j-1] + a[i][j] ——中间符号写错了。

✅ 正确是减 pre[i-1][j-1]，不是加——因为这块区域被 pre[i-1][j] 和 pre[i][j-1] 各算了两次，要减掉一次。

错 4：数组开小了导致差分越界 ​

❌ d[r+1] -= val 当 r = n 时会越界。

✅ 差分数组至少开到 n+2，避免 d[n+1] 越界。

📝 练习 ​

基础题 ​

1. 选择题

（1）前缀和 pre[i] 的定义是：
A. a[i]   B. a[1]+...+a[i]   C. a[i] - a[i-1]   D. a[i] * i

（2）差分数组 d[i] 的定义是：
A. a[i] + a[i-1]   B. a[i] - a[i-1]   C. a[i] * a[i-1]   D. pre[i] - pre[i-1]

（3）区间 [l,r] 全部加 val 的差分操作是：
A. d[l]+=val, d[r+1]-=val   B. d[l]-=val, d[r+1]+=val   C. d[l]+=val, d[r]-=val   D. d[l]-=val

2. 填空题

（1）查询一维区间 [l,r] 和的公式：pre[___] - pre[___]。

（2）二维前缀和的递推公式包含 ____ 个项（含 a[i][j]）。

（3）差分做前缀和可以还原出 ____ 数组。

提高题 ​

3. 编程题 — 区间和查询

输入 n 个数和 q 次查询。每次查询 l, r，输出 a[l]+...+a[r]。要求预处理 O(n)，查询 O(1)。

4. 编程题 — 区间修改与查询

输入 n 个初始为 0 的数，进行 m 次操作：对区间 [l,r] 加 1。输出最终每个数的值。（用差分）

挑战题 ​

5. 编程题 — 最大加权矩形

在一个 n×n 的矩阵中，找一个子矩形，使其元素和最大。输出最大和。（提示：枚举上下边界，中间用一维最大子段和）

6. 编程题 — 海底高铁

实现完整的"海底高铁"问题：n 个站，m 次移动，每段相邻站有 A（纸质票）、B（IC卡单价）、C（IC卡工本费）三种价格。求最小总花费。

🧠 本章小结 ​

前缀和 = 预处理 O(n)，查询 O(1)

一维前缀和：
  构建：pre[i] = pre[i-1] + a[i]
  查询：sum(l,r) = pre[r] - pre[l-1]

差分数组：
  构建：d[i] = a[i] - a[i-1]
  区间改：d[l]+=v, d[r+1]-=v  O(1)
  还原：前缀和 d → a       O(n)

二维前缀和（容斥原理）：
  构建：pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]
  查询：大面积 - 两条边 + 重叠角

二维差分：
  子矩阵修改 O(1)，还原用二维前缀和

核心思想：用空间换时间

📝 配套练习 ​

共8题。前缀和2题(一维+二维)→差分2题(一维+二维)→综合4题(前缀和视角+模+环形)。。★核心（课堂必做） ◆拓展（课后练习）

级别题号链接覆盖知识点
★ 核心luogu-P8218https://hydro.ac/p/luogu-P8218前缀和、区间查询O(1)
◆ 拓展luogu-P1719https://hydro.ac/p/luogu-P1719二维前缀和、子矩阵
◆ 拓展luogu-P2004https://hydro.ac/p/luogu-P2004二维前缀和、领地选择
◆ 拓展luogu-P3397https://hydro.ac/p/luogu-P3397二维差分、区间修改
◆ 拓展luogu-P1115https://hydro.ac/p/luogu-P1115前缀和视角最大子段和
◆ 拓展luogu-P2360https://hydro.ac/p/luogu-P2360二维差分、铺地毯
◆ 拓展luogu-P3131https://hydro.ac/p/luogu-P3131前缀和+模运算
◆ 拓展luogu-P5638https://hydro.ac/p/luogu-P5638前缀和、环形处理

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 7 道◆拓展题，覆盖不同变式和细节。

配套练习 ​

共8题。前缀和2题(一维+二维)→差分2题(一维+二维)→综合4题(前缀和视角+模+环形)。★核心（课堂必做） · ◆拓展（课后练习）

级别题号链接覆盖知识点
★ 核心luogu-P8218https://hydro.ac/p/luogu-P8218前缀和、区间查询O(1)
◆ 拓展luogu-P1719https://hydro.ac/p/luogu-P1719二维前缀和、子矩阵
◆ 拓展luogu-P2004https://hydro.ac/p/luogu-P2004二维前缀和、领地选择
◆ 拓展luogu-P3397https://hydro.ac/p/luogu-P3397二维差分、区间修改
◆ 拓展luogu-P1115https://hydro.ac/p/luogu-P1115前缀和视角最大子段和
◆ 拓展luogu-P2360https://hydro.ac/p/luogu-P2360二维差分、铺地毯
◆ 拓展luogu-P3131https://hydro.ac/p/luogu-P3131前缀和+模运算
◆ 拓展luogu-P5638https://hydro.ac/p/luogu-P5638前缀和、环形处理

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 7 道◆拓展题，覆盖不同变式和细节。

自查清单：

  • [ ] 我能构建一维前缀和并 O(1) 查询区间和
  • [ ] 我能用差分实现 O(1) 区间修改并还原
  • [ ] 我理解二维前缀和的容斥原理推导
  • [ ] 我能用二维前缀和查询子矩阵和
  • [ ] 我知道二维差分的四条指令
  • [ ] 我能从前缀和角度理解最大子段和问题

🚀 下章预告：前缀和很强大，但如果坐标范围是 -10⁹ 到 10⁹，数组根本开不下怎么办？下一章《压缩空间——离散化》，教你把"稀疏的大坐标"映射到"紧凑的小下标"，让前缀和、差分这些神器在大数据范围下也能施展！🗜️