二维前缀和（2D Prefix Sum） 是一维前缀和在二维上的推广，用于高效计算二维数组中任意矩形区域的元素之和。
核心思路：
prefix[i][j] 存储从左上角 (1,1) 到 (i,j) 的所有元素之和容斥原理是二维前缀和的数学基础，无论是构建还是查询都依赖它。
要求 prefix[i][j]（从 (1,1) 到 (i,j) 的总和），可以利用已经算好的前缀和拼出来：
1+-------+-------+
2| | |
3| A | B |
4| | |
5+-------+-------+
6| | (i,j) |
7| C | D |
8| | |
9+-------+-------+prefix[i-1][j] = A + B（上方）prefix[i][j-1] = A + C（左方）prefix[i-1][j-1] = A（左上角）上方 + 左方 = (A+B) + (A+C) = A+B+C + 多了一个 A，所以要减去左上角，再加上当前格 D 中 a[i][j] 的值。
构建公式：
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + a[i][j];要求从 (x1, y1) 到 (x2, y2) 的矩形区域之和，思路类似——用大矩形减去多余部分：
1+-------+-------+
2| | |
3| A | B |
4| | |
5+-------+-------+
6| |///////|
7| C |// D //| <-- D 是要求的区域
8| |///////|
9+-------+-------+prefix[x2][y2] = A+B+C+D（全部）prefix[x1-1][y2] = A+B（上方多余）prefix[x2][y1-1] = A+C（左方多余）prefix[x1-1][y1-1] = A（左上角，被多减了一次要加回来）查询公式：
sum = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1];约定：数组下标从 1 开始存储，第 0 行和第 0 列留作边界（值为 0），这样计算 prefix[i-1][j] 时不会越界。1#include <bits/stdc++.h>
2using namespace std;
3
4int a[1005][1005];
5int prefix[1005][1005];
6
7int main() {
8 int n, m, q;
9 cin >> n >> m >> q;
10
11 // 读入数据（下标从1开始）
12 for (int i = 1; i <= n; ++i)
13 for (int j = 1; j <= m; ++j)
14 cin >> a[i][j];
15
16 // 构建前缀和
17 for (int i = 1; i <= n; ++i)
18 for (int j = 1; j <= m; ++j)
19 prefix[i][j] = prefix[i-1][j] + prefix[i][j-1]
20 - prefix[i-1][j-1] + a[i][j];
21
22 // 处理q次查询
23 while (q--) {
24 int x1, y1, x2, y2;
25 cin >> x1 >> y1 >> x2 >> y2;
26 int sum = prefix[x2][y2] - prefix[x1-1][y2]
27 - prefix[x2][y1-1] + prefix[x1-1][y1-1];
28 cout << sum << endl;
29 }
30 return 0;
31}| 指标 | 值 |
|---|---|
| 预处理时间 | O(n × m) |
| 单次查询时间 | O(1) |
| 空间复杂度 | O(n × m) |
如果有 q 次查询，暴力做法每次遍历矩形区域需要 O(n × m)，总共 O(q × n × m)。使用前缀和后，预处理 O(n × m) + 查询 O(q)，当 q 较大时优势明显。
以一个 3×4 的数组为例，展示完整的构建和查询过程。
原始数组 a（下标从1开始）：
列1 列2 列3 列4
行1 [ 1 2 3 4 ]
行2 [ 5 6 7 8 ]
行3 [ 9 10 11 12 ]逐行逐列计算，每一步都套用公式 prefix[i][j] = 上 + 左 - 左上 + 当前：
| 位置 | 上 | 左 | 左上 | 当前 | 结果 |
|---|---|---|---|---|---|
| [1][1] | 0 | 0 | 0 | 1 | 1 |
| [1][2] | 0 | 1 | 0 | 2 | 3 |
| [1][3] | 0 | 3 | 0 | 3 | 6 |
| [1][4] | 0 | 6 | 0 | 4 | 10 |
| [2][1] | 1 | 0 | 0 | 5 | 6 |
| [2][2] | 3 | 6 | 1 | 6 | 14 |
| [2][3] | 6 | 14 | 3 | 7 | 24 |
| [2][4] | 10 | 24 | 6 | 8 | 36 |
| [3][1] | 6 | 0 | 0 | 9 | 15 |
| [3][2] | 14 | 15 | 6 | 10 | 33 |
| [3][3] | 24 | 33 | 14 | 11 | 54 |
| [3][4] | 36 | 54 | 24 | 12 | 78 |
前缀和数组 prefix：
列1 列2 列3 列4
行1 [ 1 3 6 10 ]
行2 [ 6 14 24 36 ]
行3 [ 15 33 54 78 ]prefix[i][j]的含义：从 (1,1) 到 (i,j) 的所有元素之和。例如prefix[2][3] = 24= 1+2+3+5+6+7 = 24。
查询：从 (2,2) 到 (3,4) 的矩形区域之和
目标区域：
列2 列3 列4
行2 [ 6 7 8 ]
行3 [ 10 11 12 ]套用公式：
sum = prefix[3][4] - prefix[1][4] - prefix[3][1] + prefix[1][1]
= 78 - 10 - 15 + 1
= 54
验证：6 + 7 + 8 + 10 + 11 + 12 = 54 ✓每个部分的含义：
prefix[3][4] = 78：整个 3×4 区域的总和prefix[1][4] = 10：上方多出的第1行（1+2+3+4）prefix[3][1] = 15：左方多出的第1列（1+5+9）prefix[1][1] = 1：左上角被多减了一次，加回来prefix[i-1][j] 时如果 i=0 会越界。建议数据从下标1开始存储，第0行第0列自然为0x1-1 和 y1-1（左上角的上一行和左一列），不要写成 x1 和 y1int 范围，需要使用 long long