题目类型：前缀和
当你发现是在求某个大的集合下一系列具体的子集时，你可以考虑下前缀和，它可以把遍历，变成值相减。
我的写法是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <vector>
#include <algorithm> // for std::max, std::min
using namespace std;
// 二维前缀和类，用于快速计算任意矩形子矩阵的和
class SumMatrix {
public:
// preSum[i][j] 表示原始矩阵中前 i 行、前 j 列（即区域 [0, i) × [0, j)）所有元素的和
// 维度为 (m+1) x (n+1)，其中 m、n 为原始矩阵的行数和列数
vector<vector<int>> preSum;
// 构造函数：根据原始矩阵 matrix 构建前缀和数组
SumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(); // 原始矩阵的行数
int n = matrix[0].size(); // 原始矩阵的列数
// 初始化前缀和数组，多一行一列用于简化边界处理
preSum.resize(m + 1, vector<int>(n + 1, 0));
// 计算前缀和：preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1]
+ matrix[i - 1][j - 1] - preSum[i - 1][j - 1];
}
}
}
// 计算原始矩阵中闭区间 [x1, x2] 行、[y1, y2] 列所围成的子矩阵的和
// 注意：x1, x2, y1, y2 都是原始矩阵的有效索引（0-based）
int Addmatrix(int x1, int x2, int y1, int y2) {
// 利用前缀和公式：sum = preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]
// 因为 preSum 的行/列索引比原始矩阵大 1，所以需要 +1 转换
return preSum[x2 + 1][y2 + 1] - preSum[x1][y2 + 1]
- preSum[x2 + 1][y1] + preSum[x1][y1];
}
};
class Solution {
public:
// 计算矩阵区域和：对于每个位置 (i, j)，求以该位置为中心、边长为 2k+1 的正方形区域的和
// （边界超出矩阵时只取有效部分）
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(); // 矩阵行数
int n = mat[0].size(); // 矩阵列数
// 结果矩阵，大小与原始矩阵相同
vector<vector<int>> answer(m, vector<int>(n, 0));
// 构建原始矩阵的前缀和对象
SumMatrix mt = SumMatrix(mat);
// 遍历每个位置 (i, j)
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 计算以 (i, j) 为中心、半径为 k 的矩形区域的边界（需限制在矩阵范围内）
int x1 = max(i - k, 0); // 上边界（行最小索引）
int x2 = min(i + k, m - 1); // 下边界（行最大索引）
int y1 = max(j - k, 0); // 左边界（列最小索引）
int y2 = min(j + k, n - 1); // 右边界（列最大索引）
// 通过前缀和快速得到该区域的和，并填入结果矩阵
answer[i][j] = mt.Addmatrix(x1, x2, y1, y2);
}
}
return answer;
}
};
|
这题说白了就是：给你一个矩阵，对于每个格子 (i,j)，把它周围 k 圈范围内的所有数加起来，填回去。
暴力做法也简单，每个格子都去遍历它的 k 邻域，但那是 $O(m \cdot n \cdot k^2)$，k 一大直接炸。
关键思路就是——前缀和把遍历变成值相减。
二维前缀和的构造其实就一句话：preSum[i][j] 表示从 (0,0) 到 (i-1, j-1) 这片矩形区域的和。多开一圈 m+1 × n+1 是为了省掉边界判空。
构造公式拆开看很直观：
1
2
3
4
| preSum[i][j] = preSum[i-1][j] // 上面那块
+ preSum[i][j-1] // 左边那块
+ matrix[i-1][j-1] // 当前这个数
- preSum[i-1][j-1] // 左上角被算了两次，扣掉
|
画个图就是：上加左，减重叠，加自己。
查子矩阵和也一个道理。想求 (x1,y1) 到 (x2,y2) 这个矩形（闭区间，0-index）的和：
1
2
3
4
| sum = preSum[x2+1][y2+1] // 整块从原点到右下
- preSum[x1][y2+1] // 砍掉上面
- preSum[x2+1][y1] // 砍掉左边
+ preSum[x1][y1] // 左上角被砍了两次，补回来
|
就是大减小，补重叠，对称得很。
最后一步，每个格子的 k 邻域怎么定界？用 max/min 把越界的部分夹住就行——左边界不能小于 0，右边界不能超过 m-1，上下同理。这样每个格子 O(1) 就能出结果，总复杂度 $O(m \cdot n)$。
一句话总结：构造一次前缀和，然后每个格子的答案就是四次查表加减。前缀和的本质就是预计算，用空间换掉内层遍历。