第 3.2 章：数组与前缀和
📝 前置条件： 确保你熟悉数组、向量和基本循环（第 2.2–2.3 章）。还需要理解
long long溢出（第 2.1 章）。
设想你有一个 N 个数字的数组，有人问你 100,000 次：「从下标 L 到 R 的元素之和是多少？」朴素做法每次重新计算——每次查询 O(N)，总计 O(N × Q)。当 N = Q = 10^5 时，是 10^10 次操作，远远太慢。
前缀和用 O(N) 预处理、每次查询 O(1) 解决这个问题。这是竞赛编程中最优雅、最实用的技术之一。
💡 核心思路： 前缀和将「区间查询」问题转化为一次减法。不用每次都从 L 到 R 求和，而是预计算累积和后做两次相减。这把
O(Q)的重复计算换成了一次性的O(N)预处理。
3.2.1 前缀和的思想
数组的前缀和是一个新数组，其中每个元素存储到当前下标为止的累积和。
图示：前缀和数组
上图展示了如何从原始数组构建前缀和数组，以及如何用 sum(L, R) = P[R] - P[L-1] 在 O(1) 时间内计算区间和。蓝色单元格标示查询范围，红绿单元格展示被相减的两个前缀值。
给定数组：A = [3, 1, 4, 1, 5, 9, 2, 6]（使用 1-indexed 以便说明）
下标： 1 2 3 4 5 6 7 8
A: 3 1 4 1 5 9 2 6
P: 3 4 8 9 14 23 25 31
其中 P[i] = A[1] + A[2] + ... + A[i]。
为什么用 1-indexed？
使用 1-indexed 数组让我们可以定义 P[0] = 0（「空前缀」和为零）。这使得查询公式 P[R] - P[L-1] 在 L = 1 时也能正常工作——计算 P[R] - P[0] = P[R]，这是正确的。
构建前缀和数组
📄 查看代码：构建前缀和数组
// 构建前缀和数组 — O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
// 第一步：读取输入（1-indexed）
vector<int> A(n + 1);
for (int i = 1; i <= n; i++) cin >> A[i];
// 第二步：构建前缀和
vector<long long> P(n + 1, 0); // P[0] = 0（基础情况）
for (int i = 1; i <= n; i++) {
P[i] = P[i - 1] + A[i]; // ← 关键行：每个 P[i] = 到 i 为止所有元素之和
}
return 0;
}
复杂度分析：
- 时间：
O(N)—— 遍历数组一次 - 空间：
O(N)—— 存储前缀数组
对 A = [3, 1, 4, 1, 5] 的逐步追踪：
i=1: P[1] = P[0] + A[1] = 0 + 3 = 3
i=2: P[2] = P[1] + A[2] = 3 + 1 = 4
i=3: P[3] = P[2] + A[3] = 4 + 4 = 8
i=4: P[4] = P[3] + A[4] = 8 + 1 = 9
i=5: P[5] = P[4] + A[5] = 9 + 5 = 14
3.2.2 O(1) 区间求和查询
有了前缀和数组，下标 L 到 R 的和就是：
sum(L, R) = P[R] - P[L-1]
为什么？ P[R] = 1..R 的元素之和。P[L-1] = 1..(L-1) 的元素之和。两者之差 = L..R 的元素之和。
💡 核心思路： 把 P[i] 理解为「前 i 个元素的总和」。要得到窗口 [L, R] 的和，就从「到 R 的前缀」中减去「L 之前的前缀」。就像：大三角形减去小三角形 = 梯形。
📄 C++ 完整代码
// 区间求和查询 — 预处理 O(N)，每次查询 O(1)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
long long A[MAXN];
long long P[MAXN];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
// 第一步：读取数组
for (int i = 1; i <= n; i++) cin >> A[i];
// 第二步：构建前缀和 — O(n)
P[0] = 0;
for (int i = 1; i <= n; i++) {
P[i] = P[i - 1] + A[i];
}
// 第三步：回答 q 个区间求和查询 — 每次 O(1)
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
cout << P[r] - P[l - 1] << "\n"; // ← 关键行：区间和公式
}
return 0;
}
样例输入：
8 3
3 1 4 1 5 9 2 6
1 4
3 7
2 6
样例输出：
9
21
20
验证：
sum(1,4) = P[4] - P[0] = 9 - 0 = 9→ A[1]+A[2]+A[3]+A[4] = 3+1+4+1 = 9 ✓sum(3,7) = P[7] - P[2] = 25 - 4 = 21→ A[3]+...+A[7] = 4+1+5+9+2 = 21 ✓sum(2,6) = P[6] - P[1] = 23 - 3 = 20→ A[2]+...+A[6] = 1+4+1+5+9 = 20 ✓
⚠️ 常见错误： 写成
P[R] - P[L]而不是P[R] - P[L-1]。公式包含 L 和 R 两个端点——你要减去 L 之前的和，不是 L 处的和。
总复杂度： O(N + Q) —— 对 N、Q 最大 10^5 完全没问题。
3.2.3 USACO 示例：品种统计
这是一道经典的 USACO Bronze 题（2015 年 12 月）。
题目： N 头奶牛排成一列，每头的品种是 1、2 或 3。回答 Q 个查询：位置 L 到 R 中有多少头品种为 B 的奶牛？
解法： 每种品种维护一个前缀和数组。
📄 C++ 完整代码
// 多品种前缀和 — O(N + Q)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
vector<int> breed(n + 1);
vector<vector<long long>> P(4, vector<long long>(n + 1, 0));
// P[b][i] = 位置 1..i 中品种 b 的奶牛数量
// 第一步：为每种品种构建前缀和
for (int i = 1; i <= n; i++) {
cin >> breed[i];
for (int b = 1; b <= 3; b++) {
P[b][i] = P[b][i - 1] + (breed[i] == b ? 1 : 0); // ← 关键行
}
}
// 第二步：每次查询 O(1) 回答
for (int i = 0; i < q; i++) {
int l, r, b;
cin >> l >> r >> b;
cout << P[b][r] - P[b][l - 1] << "\n";
}
return 0;
}
🏆 USACO 技巧： 很多 USACO Bronze 题涉及「统计范围内满足属性 X 的元素个数」。如果 Q 较大，始终考虑前缀和。
3.2.4 USACO 风格题目详解：FJ 的草地
🔗 相关题目： 这是一道受「品种统计」和「最高奶牛」启发的虚构 USACO 风格题目——两者都是经典 Bronze 题。
题目： FJ 有 N 块连续的田地，第 i 块有 grass[i] 单位的草。他需要回答 Q 个查询：「第 L 块到第 R 块（含）的草总量是多少？」N、Q 最大 10^5，每次查询需要 O(1) 回答。
样例输入：
6 4
4 2 7 1 8 3
1 3
2 5
4 6
1 6
样例输出：
13
18
12
25
逐步解法：
第一步： 理解题目。我们有数组 [4, 2, 7, 1, 8, 3]，需要区间求和。
第二步： 构建前缀和数组。
下标： 0 1 2 3 4 5 6
草量： - 4 2 7 1 8 3
P: 0 4 6 13 14 22 25
第三步： 用 P[R] - P[L-1] 回答查询：
- 查询 (1,3)：
P[3] - P[0] = 13 - 0 = 13✓ - 查询 (2,5)：
P[5] - P[1] = 22 - 4 = 18✓ - 查询 (4,6)：
P[6] - P[3] = 25 - 13 = 12✓ - 查询 (1,6)：
P[6] - P[0] = 25 - 0 = 25✓
完整 C++ 解法：
📄 C++ 完整代码
// FJ 的草地 — 前缀和解法 O(N + Q)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
// 第一步：读取草量并同步构建前缀和
vector<long long> P(n + 1, 0);
for (int i = 1; i <= n; i++) {
long long g;
cin >> g;
P[i] = P[i - 1] + g; // ← 关键行：增量前缀和
}
// 第二步：每次查询 O(1) 回答
while (q--) {
int l, r;
cin >> l >> r;
cout << P[r] - P[l - 1] << "\n";
}
return 0;
}
为什么是 O(N + Q)？
- 构建前缀和：一个循环，N 次迭代 →
O(N) - 每次查询：一次减法 → 每次
O(1)，共O(Q) - 总计：
O(N + Q)—— 远好于暴力的O(NQ)
⚠️ 常见错误： 前缀和用
int而不是long long。如果草量最大 10^9 且 N = 10^5，总和可达 10^14——远超int约 2×10^9 的范围。
3.2.5 二维前缀和
对于二维网格，可以扩展前缀和在 O(1) 时间内回答矩形区间查询。
给定 R×C 的网格，定义 P[r][c] = 从 (1,1) 到 (r,c) 矩形内所有元素之和。
构建二维前缀和
P[r][c] = A[r][c] + P[r-1][c] + P[r][c-1] - P[r-1][c-1]
减法是为了消除重叠（否则左上角矩形会被计算两次）。
💡 核心思路（容斥原理）： 想象四个矩形：
P[r-1][c]= 「上方」矩形P[r][c-1]= 「左方」矩形P[r-1][c-1]= 「左上角」（在上面两个中都计算了——所以减去一次）A[r][c]= 单个新单元格
二维前缀和逐步工作示例
追踪一个 4×4 网格：
原始网格 A：
c=1 c=2 c=3 c=4
r=1: 1 2 3 4
r=2: 5 6 7 8
r=3: 9 10 11 12
r=4: 13 14 15 16
逐步构建 P（从左到右、从上到下）：
📄 Code 完整代码
P[1][1] = A[1][1] = 1
P[1][2] = 2 + 0 + 1 - 0 = 3
P[1][3] = 3 + 0 + 3 - 0 = 6
P[1][4] = 4 + 0 + 6 - 0 = 10
P[2][1] = 5 + 1 + 0 - 0 = 6
P[2][2] = 6 + 3 + 6 - 1 = 14
P[2][3] = 7 + 6 + 14 - 3 = 24
P[2][4] = 8 + 10 + 24 - 6 = 36
P[3][1] = 9 + 6 + 0 - 0 = 15
P[3][2] = 10 + 14 + 15 - 6 = 33
P[3][3] = 11 + 24 + 33 - 14 = 54
P[3][4] = 12 + 36 + 54 - 24 = 78
P[4][1] = 13 + 15 + 0 - 0 = 28
P[4][2] = 14 + 33 + 28 - 15 = 60
P[4][3] = 15 + 54 + 60 - 33 = 96
P[4][4] = 16 + 78 + 96 - 54 = 136
前缀和网格 P：
c=1 c=2 c=3 c=4
r=1: 1 3 6 10
r=2: 6 14 24 36
r=3: 15 33 54 78
r=4: 28 60 96 136
查询：子网格 (r1=2, c1=2) 到 (r2=3, c2=3) 的和：
ans = P[3][3] - P[1][3] - P[3][1] + P[1][1]
= 54 - 6 - 15 + 1
= 34
验证：A[2][2]+A[2][3]+A[3][2]+A[3][3] = 6+7+10+11 = 34 ✓
容斥原理图示：
📄 C++ 完整代码
// 二维前缀和 — 构建 O(R×C)，查询 O(1)
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 1001, MAXC = 1001;
int A[MAXR][MAXC];
long long P[MAXR][MAXC];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int R, C;
cin >> R >> C;
for (int r = 1; r <= R; r++)
for (int c = 1; c <= C; c++)
cin >> A[r][c];
// 第一步：构建二维前缀和 — O(R × C)
for (int r = 1; r <= R; r++) {
for (int c = 1; c <= C; c++) {
P[r][c] = A[r][c]
+ P[r-1][c] // 上方矩形
+ P[r][c-1] // 左方矩形
- P[r-1][c-1]; // ← 关键行：消除重叠（被计算了两次）
}
}
// 第二步：每次查询 O(1) 回答
int q;
cin >> q;
while (q--) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
long long ans = P[r2][c2]
- P[r1-1][c2] // 减去上方条带
- P[r2][c1-1] // 减去左方条带
+ P[r1-1][c1-1]; // 加回左上角
cout << ans << "\n";
}
return 0;
}
复杂度分析：
- 构建时间：
O(R × C) - 查询时间： 每次
O(1) - 空间：
O(R × C)
⚠️ 常见错误： 查询公式中忘记加回
P[r1-1][c1-1]。上方条带和左方条带都包含左上角，所以被减了两次——需要加回一次！
3.2.6 差分数组
既然你已经看到二维前缀和如何将一维思想扩展到网格，让我们来看对偶操作：差分数组。就像微积分中微分是积分的逆运算，差分数组是前缀和的逆运算——前缀和将点数据累积成区间数据，差分数组将区间操作分解为点标记。
| 方向 | 操作 | 类比 |
|---|---|---|
| 正向：前缀和 | 点值 → 区间和 | 积分 ∫ |
| 逆向：差分数组 | 区间更新 → 点标记 | 微分 d/dx |
这种对偶性很强大：要高效地执行区间更新，只需在差分数组中标记边界，最后取前缀和恢复最终结果。
问题： 从全零开始，执行 M 次更新：「给位置 L 到 R 的所有元素加 V」，然后打印最终数组。
朴素做法每次更新是 O(R-L+1)。用差分数组，每次更新是 O(1)，重建是 O(N)。
💡 核心思路： 不是给 [L, R] 中每个位置加 V（慢），而是记录「在位置 L 加 V」和「在位置 R+1 减 V」（快）。之后对这些标记取前缀和，+V 和 -V 在 [L,R] 外相互抵消，净效果恰好是给 [L,R] 加了 V。
📄 C++ 完整代码
// 差分数组实现区间更新 — O(N + M)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<long long> diff(n + 2, 0); // 差分数组（多一位空间用于 R+1 情况）
// 第一步：每次 O(1) 处理所有区间更新
for (int i = 0; i < m; i++) {
int l, r, v;
cin >> l >> r >> v;
diff[l] += v; // ← 关键行：标记区间起点
diff[r + 1] -= v; // ← 关键行：标记终点+1 以撤销加法
}
// 第二步：对 diff 取前缀和，重建最终数组
long long running = 0;
for (int i = 1; i <= n; i++) {
running += diff[i];
cout << running;
if (i < n) cout << " ";
}
cout << "\n";
return 0;
}
样例输入：
5 3
1 3 2
2 5 3
3 4 -1
逐步追踪：
📝 索引说明： 以下追踪中 diff 数组使用 1-indexed（即 diff[1]..diff[n+1]），与代码一致。
📄 Code 完整代码
初始状态: diff[1..6] = [0, 0, 0, 0, 0, 0]
更新(1,3,+2): diff[1]+=2, diff[4]-=2
diff[1..6] = [2, 0, 0, -2, 0, 0]
更新(2,5,+3): diff[2]+=3, diff[6]-=3
diff[1..6] = [2, 3, 0, -2, 0, -3]
更新(3,4,-1): diff[3]-=1, diff[5]+=1
diff[1..6] = [2, 3, -1, -2, 1, -3]
前缀和重建：
i=1: running = 0+2 = 2 → result[1] = 2
i=2: running = 2+3 = 5 → result[2] = 5
i=3: running = 5-1 = 4 → result[3] = 4
i=4: running = 4-2 = 2 → result[4] = 2
i=5: running = 2+1 = 3 → result[5] = 3
样例输出：
2 5 4 2 3
复杂度分析：
- 时间：
O(N + M)—— 每次更新O(1)，重建O(N) - 空间：
O(N)—— 只需差分数组
⚠️ 常见错误： 将
diff声明为 N+1 而非 N+2。当 R=N 时，需要写入diff[R+1] = diff[N+1]，它必须存在！
3.2.7 二维差分数组
就像一维差分数组是一维前缀和的逆，二维差分数组是二维前缀和的逆。它可以在 O(1) 时间内给整个矩形子网格 [r1,c1]..[r2,c2] 加一个值 V。
四角更新
给矩形 [r1,c1] 到 [r2,c2] 的所有单元格加 V，在差分数组的四个角标记：
diff[r1][c1] += V // 矩形起始
diff[r1][c2+1] -= V // 取消右侧溢出
diff[r2+1][c1] -= V // 取消下方溢出
diff[r2+1][c2+1] += V // 加回被双重取消的角
这是一维技巧 diff[L] += V; diff[R+1] -= V 的二维类比。所有更新后，对差分数组取二维前缀和以恢复最终值。
💡 核心思路： 四角标记正好是二维前缀和查询公式的逆运算。查询中我们减去两个条带然后加回一个角；更新中我们加上两个条带然后减去一个角。它们是镜像操作！
完整 C++ 实现
📄 查看代码：完整 C++ 实现
// 二维差分数组 — 每次更新 O(1)，重建 O(RC)
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 1002, MAXC = 1002;
long long diff[MAXR][MAXC]; // 额外行列用于哨兵
void update(int r1, int c1, int r2, int c2, long long V) {
diff[r1][c1] += V; // ← 左上角
diff[r1][c2+1] -= V; // ← 右上+1
diff[r2+1][c1] -= V; // ← 下+1左
diff[r2+1][c2+1] += V; // ← 下+1右+1（加回）
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int R, C, M;
cin >> R >> C >> M;
memset(diff, 0, sizeof diff);
// 第一步：每次 O(1) 应用所有矩形更新
for (int i = 0; i < M; i++) {
int r1, c1, r2, c2;
long long V;
cin >> r1 >> c1 >> r2 >> c2 >> V;
update(r1, c1, r2, c2, V);
}
// 第二步：通过二维前缀和重建 — O(R × C)
for (int r = 1; r <= R; r++)
for (int c = 1; c <= C; c++)
diff[r][c] += diff[r-1][c] + diff[r][c-1] - diff[r-1][c-1];
// 现在 diff[r][c] 存储 (r,c) 处的最终值
for (int r = 1; r <= R; r++) {
for (int c = 1; c <= C; c++) {
cout << diff[r][c];
if (c < C) cout << " ";
}
cout << "\n";
}
return 0;
}
工作示例
一个 3×3 网格，初始全零，两次更新：
update(1,1, 2,2, +5)—— 给左上 2×2 块加 5update(2,2, 3,3, +3)—— 给右下 2×2 块加 3
标记 diff[][] 后：
c=0 c=1 c=2 c=3 c=4
r=0: 0 0 0 0 0
r=1: 0 +5 0 -5 0
r=2: 0 0 +3 0 -3
r=3: 0 -5 0 +5 0
r=4: 0 0 -3 0 +3
二维前缀和重建后：
c=1 c=2 c=3
r=1: 5 5 0
r=2: 5 8 3
r=3: 0 3 3
验证：单元格 (2,2) = 5+3 = 8 ✓（被两次更新都覆盖）。
复杂度分析：
- 更新时间： 每次矩形
O(1)—— 只有 4 次加法 - 重建时间：
O(R × C)—— 一次二维前缀和遍历 - 空间：
O(R × C)
⚠️ 常见错误： 将差分数组声明为
diff[R+1][C+1]而非diff[R+2][C+2]。当r2=R、c2=C时，需要写入diff[R+1][C+1]，它必须存在！
3.2.8 USACO 示例：最大子数组和
题目（Kadane 算法的变体）： 找连续子数组的最大和。
📄 C++ 完整代码
// Kadane 算法 — O(N) 时间，O(1) 空间
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<int> A(n);
for (int &x : A) cin >> x;
// Kadane 算法：O(n)
long long maxSum = LLONG_MIN; // 最小 long long
long long current = 0;
for (int i = 0; i < n; i++) {
current += A[i];
maxSum = max(maxSum, current);
if (current < 0) current = 0; // ← 关键行：和为负时重新开始
}
cout << maxSum << "\n";
return 0;
}
💡 核心思路： 为什么当 current 为负时重置为 0？因为负的前缀和只会损害之后的任何子数组。如果当前运行和是 -5，任何从头开始（和为 0）的子数组都比继续 -5 要好。
用前缀和的替代方案： 最大子数组和等于 P[j] - P[i-1] 对所有对 (i,j) 的最大值。对于每个 j，当 P[i-1] 最小时取得最大。追踪运行中最小前缀和！
// 替代方案：最小前缀技巧 — 同样 O(N)
long long maxSum = LLONG_MIN, minPrefix = 0, prefix = 0;
for (int x : A) {
prefix += x;
maxSum = max(maxSum, prefix - minPrefix); // 到此处结束的最优和
minPrefix = min(minPrefix, prefix); // 追踪目前见过的最小前缀
// ⚠️ 注意：minPrefix 的更新必须在 maxSum 之后。
// 若提前更新 minPrefix，相当于允许空子数组（长度为0）参与比较，
// 会导致结果在全负数组时错误地返回 0 而非最大负数。
}
⚠️ 第 3.2 章常见错误
- 区间查询差一： 写
P[R] - P[L]而不是P[R] - P[L-1]。始终用小例子验证。 - 溢出： 大值的前缀和可能超过
int范围（2×10^9）。即使元素是int，前缀数组也要用long long。 - 二维查询公式： 忘了二维查询中的
+P[r1-1][c1-1]项——非常容易疏忽。 - 差分数组大小： 声明
diff[n+1]但需要diff[n+2]（因为要写入下标r+1，可能是n+1）。 - 1-indexed vs 0-indexed： 用 0-indexed 前缀和时，查询公式变为
P[R+1] - P[L]。在一道题内选定一种约定并坚持用。 - 二维差分数组大小： 声明
diff[R+1][C+1]但需要diff[R+2][C+2]——四角更新会写入(r2+1, c2+1)，必须在范围内。 - 二维差分重建顺序： 二维前缀和重建必须从左到右、从上到下处理单元格（与构建二维前缀和的顺序相同）。顺序混乱会产生错误结果。
本章总结
📌 核心要点
| 技术 | 构建时间 | 查询时间 | 空间 | 使用场景 |
|---|---|---|---|---|
| 一维前缀和 | O(N) | O(1) | O(N) | 一维数组的区间和 |
| 二维前缀和 | O(RC) | O(1) | O(RC) | 二维网格的矩形和 |
| 差分数组 | O(N+M) | O(1)* | O(N) | 区间加法更新 |
| 二维差分数组 | O(RC+M) | O(1)* | O(RC) | 二维网格上的矩形加法 |
| Kadane 算法 | O(N) | — | O(1) | 最大子数组和 |
*需要 O(N) 的重建遍历后才能读取所有值。
🧩 核心公式速查
| 操作 | 公式 | 备注 |
|---|---|---|
| 一维区间和 | P[R] - P[L-1] | P[0] = 0 是哨兵值 |
| 二维矩形和 | P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1] | 容斥：减两次，加一次 |
| 差分数组更新 | diff[L] += V; diff[R+1] -= V; | 数组大小应为 N+2 |
| 二维差分更新 | diff[r1][c1]+=V; diff[r1][c2+1]-=V; diff[r2+1][c1]-=V; diff[r2+1][c2+1]+=V | 四角标记 |
| 从差分恢复 | 对 diff 取前缀和（一维或二维） | 结果是最终数组 |
❓ 常见问题
Q1：前缀和和差分数组有什么关系？
A：它们是逆运算。对数组取前缀和得到前缀和数组；对前缀和数组取差分（相邻元素差）则恢复原数组。反过来，对差分数组取前缀和也能恢复原数组。这类似于数学中的积分和微分。
Q2：什么时候用前缀和 vs 差分数组？
A：经验法则——看操作类型：
- 多次区间求和查询 → 前缀和（预处理
O(N)，查询O(1)）- 多次区间加减操作 → 差分数组（更新
O(1)，最后恢复O(N)）- 两种操作交替出现时，需要更高级的数据结构（如第 3.9 章的线段树）
Q3：前缀和能处理动态修改吗？（数组元素改变）
A：不能。前缀和是一次性预处理，之后数组不能改变。如果元素被修改，用树状数组（BIT）或线段树，它们支持单点更新和
O(log N)的区间查询。
Q4：为什么 Kadane 算法有两个版本（current=0 vs minPrefix）？
A：两者本质相同，都是
O(N)。第一种（经典 Kadane）更直觉：当前子数组和变负时重新开始。第二种（最小前缀法）用前缀和思维：最大子数组 = max(P[j] - P[i]) = max(P[j]) - min(P[i])。按个人喜好选择。
Q5：二维前缀和的空间限制是什么？
A：若 R、C 都最大 10^4，P 数组需要 10^8 个
long long（约 800MB）——超出内存限制。一般 R×C ≤ 10^6~10^7 是安全的。更大的网格考虑压缩或离线处理。
🔗 与后续章节的联系
- 第 3.4 章（双指针）：滑动窗口也能做区间查询，但只适用于固定大小或单调移动的窗口；前缀和更通用
- 第 3.3 章（排序与搜索）：二分查找可以与前缀和结合——例如在前缀和数组上二分查找第一个 ≥ 目标值的位置
- 第 3.9 章（线段树）：解决前缀和无法处理的「动态更新 + 区间查询」问题
- 第 6.1–6.3 章（动态规划）：很多状态转移涉及区间和；前缀和是优化 DP 的重要工具
- 差分数组的思想（「在起点 +V，在终点后 -V」）在扫描线算法、事件排序等高级技术中反复出现
练习题
题目 3.2.1 — 区间求和 🟢 简单 读取 N 个整数和 Q 个查询，每个查询给出 L 和 R，打印下标 L 到 R（1-indexed）的元素之和。
提示
构建前缀和数组 P，其中 P[i] = A[1]+...+A[i]，每次查询回答 P[R] - P[L-1]。✅ 完整题解
核心思路： O(N) 预计算前缀和，每次查询 O(1) 回答 P[R] - P[L-1]。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, q; cin >> n >> q;
vector<long long> P(n + 1, 0);
for (int i = 1; i <= n; i++) {
int x; cin >> x;
P[i] = P[i-1] + x;
}
while (q--) {
int l, r; cin >> l >> r;
cout << P[r] - P[l-1] << "\n";
}
}
复杂度： O(N + Q) —— 远好于朴素 O(N × Q)。
题目 3.2.2 — 区间加法，单点查询 🟢 简单 从 N 个零开始，处理 M 次操作：每次给 L 到 R 的所有位置加 V。所有操作后打印每个位置的值。
提示
对每次更新用 `diff[L]` += V，`diff[R+1]` -= V，然后对 diff 取前缀和。✅ 完整题解
核心思路： 差分数组。每次区间加法只影响 diff 的 2 个位置，最终值通过前缀和得到。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m; cin >> n >> m;
vector<long long> diff(n + 2, 0);
while (m--) {
int l, r; long long v; cin >> l >> r >> v;
diff[l] += v;
diff[r+1] -= v;
}
long long cur = 0;
for (int i = 1; i <= n; i++) {
cur += diff[i];
cout << cur << " \n"[i == n];
}
}
复杂度： O(N + M) —— 每次更新 O(1)，最后扫描 O(N)。
题目 3.2.3 — 矩形求和 🟡 中等
读取 N×M 网格和 Q 个查询，每个查询给出 (r1,c1,r2,c2)，打印子网格的和。
提示
二维前缀和。查询 = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]。✅ 完整题解
核心思路： 二维前缀和。P[i][j] = 从 (1,1) 到 (i,j) 的矩形和，对任意矩形查询用容斥相减。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, m, q; cin >> n >> m >> q;
vector<vector<long long>> P(n+1, vector<long long>(m+1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int x; cin >> x;
P[i][j] = x + P[i-1][j] + P[i][j-1] - P[i-1][j-1];
}
while (q--) {
int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
cout << P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1] << "\n";
}
}
复杂度： O(N × M + Q)。
题目 3.2.4 — USACO 2016 January Bronze：割草 🔴 困难 FJ 沿一条路径割草，被访问超过一次的格子构成「双重割草」区域，统计至少被访问两次的格子数。
提示
模拟路径，在二维访问计数中标记格子，统计值 ≥ 2 的格子。✅ 完整题解
核心思路： 直接模拟——不需要复杂数据结构。沿路径走，对每个访问的格子递增二维计数器。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
map<pair<int,int>, int> cnt;
int x = 0, y = 0; cnt[{x,y}]++;
while (n--) {
char dir; int steps; cin >> dir >> steps;
int dx = (dir=='E') - (dir=='W');
int dy = (dir=='N') - (dir=='S');
while (steps--) {
x += dx; y += dy;
cnt[{x,y}]++;
}
}
int doubleMowed = 0;
for (auto& [pos, c] : cnt) if (c >= 2) doubleMowed++;
cout << doubleMowed << "\n";
}
复杂度： O(总步数 × log)，受 map 操作主导。
题目 3.2.5 — 二维区间加法 🟡 中等
N×M 网格（初始全零），Q 次操作每次给矩形 [r1,c1] 到 [r2,c2] 加 V，输出最终网格。
提示
二维差分数组：每次更新标记 4 个角，然后通过二维前缀和重建。✅ 完整题解
核心思路： 二维差分数组。每次矩形更新只触及 4 个角。最终网格 = 差分数组的二维前缀和。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, q; cin >> n >> m >> q;
vector<vector<long long>> D(n+2, vector<long long>(m+2, 0));
while (q--) {
int r1, c1, r2, c2; long long v;
cin >> r1 >> c1 >> r2 >> c2 >> v;
D[r1][c1] += v;
D[r1][c2+1] -= v;
D[r2+1][c1] -= v;
D[r2+1][c2+1] += v;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
D[i][j] += D[i-1][j] + D[i][j-1] - D[i-1][j-1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cout << D[i][j] << " \n"[j == m];
}
复杂度： O(Q + N × M)。
题目 3.2.6 — 最大子数组（Kadane 算法） 🟡 中等 读取 N 个整数（可能为负），找连续子数组的最大和。
提示
Kadane 算法。如果所有数都是负数，答案 = 最大的单个元素。✅ 完整题解
核心思路： 在每个位置，要么开始新的子数组，要么延伸当前的。cur = max(A[i], cur + A[i])，追踪最优值。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
long long best = LLONG_MIN, cur = 0;
for (int i = 0; i < n; i++) {
long long x; cin >> x;
cur = max(x, cur + x);
best = max(best, cur);
}
cout << best << "\n";
}
为什么当 cur+x < x 时从头开始？ 因为负的运行和只会损害未来的项——丢弃它，从当前元素重新开始。
追踪 [-2, 1, -3, 4, -1, 2, 1, -5, 4]：
x=-2: cur=-2, best=-2
x=1: cur=max(1,-2+1)=1, best=1
x=-3: cur=max(-3,1-3)=-2, best=1
x=4: cur=max(4,-2+4)=4, best=4
x=-1: cur=max(-1,4-1)=3, best=4
x=2: cur=5, best=5
x=1: cur=6, best=6 ✓
x=-5: cur=1, best=6
x=4: cur=5, best=6
复杂度： O(N) 时间，O(1) 空间。
🏆 挑战题：奶牛与油漆桶 N×M 网格中有油漆桶，每个有一个正值。选择任意矩形子网格。得分 = (子网格最大值) - (边界格子之和)。找最优矩形。（N, M ≤ 500）
✅ 解题思路
朴素枚举所有 O(N²M²) 矩形对 500² 来说太慢。改进方案：
- 用二维前缀和实现 O(1) 求和查询
- 对子网格中的最大值：预处理二维稀疏表（或每行 RMQ）实现 O(1) 最大值查询
- 边界和 = 总和 - 内部和（均通过前缀和）
总计：O(N²M²) 枚举 × O(1) 每次查询 = 对 N,M ≤ 500 在时间限制内。