Lesson 0415 · 前缀和 / 差分 / 单调栈

④ 数据结构与算法 — 第 15 课

1. 前缀和：把「一段」变成「两个前缀相减」

问题：数组 a[1..n]，多次问「第 l 个数到第 r 个数的和」。朴素做法每次都要累加 r-l+1 个数，q 次询问就是 O(nq)。

前缀和的想法是：先花 O(n) 把「从第 1 个数加到第 i 个数」全部算出来，之后任何区间和都是一次减法：

s[0] = 0;
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

// 区间 [l, r] 的和
long long sum = s[r] - s[l - 1];

为什么对：s[r] 是「前 r 个」，s[l-1] 是「前 l−1 个」，减掉后面那段不要的，剩下的正好是 [l, r]。注意下标要减 l−1 而不是 l —— 这是最常错的地方。

变体：取模的前缀和（P3131 就是它）

P3131 问「和能被 7 整除的最长连续段」。这里不需要区间和的具体值，只需要它 mod 7 的结果：

int first[7];
fill(first, first + 7, -1);
first[0] = 0;                        // 余数 0 在「第 0 个位置」就已经出现过
int best = 0, pre = 0;
for (int i = 1; i <= n; i++) {
    pre = (pre + a[i]) % 7;
    if (first[pre] == -1) first[pre] = i;          // 第一次见，记下位置
    else best = max(best, i - first[pre]);         // 又见到了 → 中间这一段能被 7 整除
}

实测（本机）：n = 50000 时耗时 0.20 ms，答案与 O(n²) 暴力枚举 500 组随机数据完全一致（0 组不一致）。样例 3 5 1 6 2 14 10 输出 5，与题解一致。

2. 二维前缀和：容斥

矩阵里的区间求和，思路一样，只是「前缀」变成了「左上角到 (i,j) 这一整块的矩形」。递推要减去重叠部分、再补回被减两次的：

s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + g[i][j];

查询 (x1, y1) 到 (x2, y2) 这个子矩形的和，同样是四次：

sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];

实测一张 3×4 的矩阵（1..12 按行填），前缀和表是：

查 (2,2)–(3,3)：程序算出来是 34，手算 6+7+10+11 = 34，公式为 s[3][3] − s[1][3] − s[3][1] + s[1][1] = 54 − 6 − 15 + 1 = 34。注意减的是 x1−1 那一行（第 1 行），不是第 2 行。

3. 差分：区间加只改两个位置

问题换成：数组 a[1..n]，p 次「把 [x, y] 每个数加 z」，最后问最小值。朴素做法每次都要改 y-x+1 个数。

差分的想法：不直接改区间，改「区间开始的地方 +z、结束的后一位 −z」。最后从头累加一遍，变化就自动「铺」到整个区间上；出了区间又被那个 -z 抵消掉。

// d 是差分数组，多开一位（y+1 可能等于 n+1）
vector<int> d(n + 2, 0);
for (int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];   // 先变成差分

for (每次操作 x y z) { d[x] += z; d[y + 1] -= z; }

// 还原并顺便取最小
int cur = 0, mn = INT_MAX;
for (int i = 1; i <= n; i++) { cur += d[i]; mn = min(mn, cur); }

实测一组小数据：b = 5 3 8 1 4 9，做三次操作（[2,4] 加 3、[1,3] 加 −2、[5,6] 加 7），差分还原后是

手算核对：位置 1 只吃 −2 → 3；位置 2 吃 +3 和 −2 → 4；位置 4 只吃 +3 → 4；位置 5 只吃 +7 → 11。全对。

P2367 的实测对比

同一组数据朴素的做法要 257 ms，差分只要 0.28 ms —— 差了约 900 倍。而到了本题上限（5×10⁶），朴素做法根本跑不完，差分仍然只要 75 ms。

4. 单调栈：每个元素只进一次、出一次

P5788 问：对每个 i，找到它右边第一个比 a[i] 大的数的下标，没有就输出 0。朴素是 O(n²)。

换个方向想：从右往左扫，维护一个栈，栈里存「还没找到答案的下标」，并且保证从栈底到栈顶，数值递减（栈顶最小）。新来一个 a[i] 时：

1. 栈里所有 ≤ a[i] 的下标，它们的答案不可能是 i（因为 i 更靠左，且值不比它们大）—— 直接弹掉，而且以后再也不会用到。
2. 弹完之后，栈顶就是「右边第一个比 a[i] 大的数」。
3. 把 i 压进去。

vector<int> f(n + 1, 0), st;      // 1-based
for (int i = n; i >= 1; i--) {
    while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();
    f[i] = st.empty() ? 0 : st.back();
    st.push_back(i);
}

实测 a = 2 1 4 5 3：

输出 3 3 4 0 0，与 O(n²) 暴力在 500 组随机数据上完全一致。n = 3×10⁶（本题上限）实测 23.4 ms。

变体：下一个更小

只需要把比较符号反过来：while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();。同一组 2 1 4 5 3 的下一个更小是 2 0 5 5 0（实测）。

5. 三件工具怎么选

6. 三道题的题面要点

7. 坑点清单

• 前缀和的下标：区间是 s[r] - s[l-1]，不是 s[r] - s[l]
• 前缀和开 long long：n 个 10⁹ 就是 10¹⁴
• P3131 的 first[0] = 0：忘了它，答案会少掉「从第一个数开始」的那一段
• 二维前缀和的四个下标：减 x1-1、y1-1，加 x1-1, y1-1
• 差分数组多开两位：d[y+1] -= z 可能写到 n+1
• 差分用完要「前缀和还原」，别直接拿 d 当答案
• 单调栈的 <= 与 <：求「第一个严格更大」用 <= 弹；求「第一个大于等于」用 < 弹
• 单调栈存下标：存值的话就没法输出下标，也没法比较

8. 小测

9. 动手练习

1. P3131 Subsequences Summing to Sevens S —— N ≤ 5×10⁴。三个必须自己踩的点：① first[0] = 0 别忘了；② 只有 7 个余数，用数组存「第一次出现位置」就够；③ 答案是长度，不是和。
2. P2367 语文成绩 —— n ≤ 5×10⁶，读入量很大，必须快读。差分数组开 n+2；最后一遍累加时顺便取最小值。
3. P5788 【模板】单调栈 —— n ≤ 3×10⁶。栈里存下标；不存在输出 0；答案用空格隔开。
4. 选做：下一个更小 —— 把 P5788 的代码改一个符号，自己造几组数据验证。

本课小结

• 前缀和：s[i] = s[i-1] + a[i]，区间和 s[r] - s[l-1]，O(1) 查询
• 取模前缀和：同一余数之间的那段，和被模数整除（P3131 的核心）
• 二维前缀和：容斥 —— 加两次、减一次，查询四角
• 差分：区间加只改 d[x] += z 和 d[y+1] -= z，最后累加还原
• 单调栈：从右往左扫，弹掉「不可能是答案」的，栈顶即答案；每元素进出各一次，O(n)
• 实测：P2367 朴素 257 ms vs 差分 0.28 ms；P5788 n=3×10⁶ → 23.4 ms