RED韵刷到 LCR_013 这道题，题目名字叫“二维区域和检索 - 矩阵不可变”，核心知识点就挂在标题上——前缀和。刚接触前缀和的读者可能会觉得这是典型的竞赛技巧，离日常业务很远，但说实话，我见过太多性能问题最后就是用一张前缀和表解决的。比如统计报表里频繁查询某个矩形区域的总销售额、图像处理里计算滑动窗口内的像素总和，本质都是同一个问题：给定一个静态矩阵，反复求任意子矩阵的和。暴力做法每次查询都要把矩形里的元素重新加一遍，查询一多，耗时直线上升，而前缀和可以把每次查询的时间压到 O(1)，代价仅仅是初始化时多付出 O(m×n) 的时间和一个等规模的空间。这篇文章就围绕这道题，把一维前缀和怎么推广到二维、预处理怎么算、查询公式怎么推、编码时有哪些细节坑，全部捋一遍。
1. 题目拆解：先看清“不可变”三个字的分量
1.1 需求边界决定方案走向
LCR_013 的题目描述很简短：给定一个二维矩阵 matrix，实现一个类，构造函数接收矩阵，之后反复调用 sumRegion(row1, col1, row2, col2) 返回左上角 (row1, col1) 到右下角 (row2, col2) 这个矩形区域内所有元素之和。题目明确写着“矩阵不可变”，这四个字是整个题眼。
很多读者第一次看到这道题时，注意力全放在“怎么快速求矩形和”上，容易忽略“不可变”才是决定方案的前提。如果矩阵是静态的，那么预处理、建立索引、构建缓存都是划算的；如果矩阵里元素会被频繁修改，那静态前缀和的方案就要打折扣，因为单点更新会导致整张前缀和表大面积失效，更新成本可能高达 O(m×n)。所以拿到这类“检索类”题目，第一件事是确认数据是否可变。可变有可变的解法（树状数组、线段树），不可变才有资格谈一次性预处理。
1.2 暴力解法为什么撑不住高频查询
最容易想到的方案是每次调用 sumRegion 时直接两层循环累加：
cpp复制int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int i = row1; i <= row2; ++i)
for (int j = col1; j <= col2; ++j)
sum += matrix[i][j];
return sum;
}
这个解法单次查询的时间复杂度是 O(row2-row1+1) × O(col2-col1+1)，最坏情况下，如果查询区域覆盖整个矩阵，就是 O(m×n)。假设矩阵是 1000×1000，一次全区域查询就要累加 100 万个数。如果业务方调用接口做统计分析，一秒钟来几百次查询，CPU 全耗在重复加法上。
更致命的是，如果查询区间很小，每次只加几个数，看起来开销低，但调用方往往会做循环。比如在一个大矩阵上滑动窗口统计各种尺寸子矩阵的和，窗口数量本身就有 O(n²) 级别，再乘以每个窗口的累加成本，整体复杂度直接爆炸。暴力方案不是不能用，而是只适合“矩阵小 + 查询少”的场景，面试题和真实系统都不可能接受这种设计。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 二维前缀和：站在一维的肩膀上
2.1 先回顾一维前缀和的思想
一维前缀和很多人都熟。给定数组 nums，预先计算 pre[i] = pre[i-1] + nums[i]，表示 nums[0] 到 nums[i-1] 的累计和，这里我把 pre 定义为前 i 个元素的和（长度 n+1），这样处理边界最舒服。区间 [l, r] 的和就能写成 pre[r+1] - pre[l]，一次减法搞定。
为什么要偏移一位？因为当 l = 0 时，pre[0] 正好是空数组的和 0，公式不用单独特判。这是编码里非常关键的细节，很多人在一维前缀和上就吃过亏，要么把前缀和数组开成 n 大小导致 pre[l-1] 越界，要么对 l=0 的情况单独分支。升到二维之后，偏移一位带来的便利会被放大，因为二维的边界条件不止左边界，还有上边界，两个方向同时偏移，能省掉整整一类判断。
2.2 二维前缀和的定义与容斥原理
二维前缀和的定义是这样：pre[i][j] 表示从矩阵左上角 (0, 0) 开始，到 (i-1, j-1) 为止的矩形区域内所有元素的和。注意，这里 pre[i][j] 对应的是前 i 行、前 j 列，不是下标 (i, j) 本身。这个偏移约定和一位前缀和保持一致，目的还是为了让边界处理统一。
有了定义，构造过程就靠容斥原理。想象 pre[i][j] 所覆盖的矩形，它可以看作三部分组合：
- 前 i-1 行、前 j 列的区域，即 pre[i-1][j]
- 前 i 行、前 j-1 列的区域，即 pre[i][j-1]
- 单独的 matrix[i-1][j-1] 这个元素
但直接相加会重复计算前 i-1 行、前 j-1 列那块公共区域，也就是 pre[i-1][j-1]。所以要减掉一次。
写出来就是：
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1]
这个公式是整个算法的核心。读者可以自己画一个 3×3 的矩阵，把 pre 表手推一遍。我当年学到这里时，第一次看这个公式觉得它很绕，后来悟到“容斥”两个字就通了——两个矩形相加，重叠部分被算了两次，必须扣掉。查一个任意子矩阵时同样用容斥，只是方向反过来。
2.3 查询公式是怎么推出来的
假设要查询左上角 (row1, col1)、右下角 (row2, col2) 的矩形和。利用 pre 表，可以先取出一个更大的矩形：从 (0, 0) 到 (row2, col2)，也就是 pre[row2+1][col2+1]。
这个大矩形 = 目标区域 + 上方多余区域 + 左侧多余区域 + 左上角多余区域。想要得到目标区域，需要从大矩形里减去上方区域（前 row1 行、前 col2+1 列），再减去左侧区域（前 row2+1 行、前 col1 列）。
但这样左上角那块被减了两次，它对应的是前 row1 行、前 col1 列，也就是 pre[row1][col1]，需要再加回来一次。
所以查询公式是：
sumRegion = pre[row2+1][col2+1] - pre[row1][col2+1] - pre[row2+1][col1] + pre[row1][col1]
我第一次写的时候老记混四个下标，后来总结了个土办法：分子区域有两个坐标，row2 和 col2 都出现在加号上，row1 和 col1 分别出现在两个减号里，而 pre[row1][col1] 那个是“补回来的”。只要心里清楚 pre 表每一位都比实际坐标偏移一格，公式就不会错。
3. 代码实现与关键细节解析
3.1 完整可运行的 C++ 实现
直接上代码，这套写法我个人认为是这道题的标准答案，简洁且不容易出边界错：
cpp复制class NumMatrix {
private:
vector<vector<int>> pre;
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m == 0) return;
int n = matrix[0].size();
pre.resize(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return pre[row2 + 1][col2 + 1] - pre[row1][col2 + 1] - pre[row2 + 1][col1] + pre[row1][col1];
}
};
构造函数里先判断 m == 0，是因为如果矩阵一行都没有，matrix[0] 本身就是非法访问。n 的取值必须放在判空之后。pre 的尺寸开成 (m+1)×(n+1)，所有下标从 1 开始填，第 0 行和第 0 列全部保持 0，正好用来处理“前 0 行”和“前 0 列”的边界情况。
3.2 Python 实现与内存布局
Python 版本同样直观：
python复制from typing import List
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
m = len(matrix)
if m == 0:
return
n = len(matrix[0])
self.pre = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
self.pre[i][j] = (self.pre[i - 1][j] + self.pre[i][j - 1]
- self.pre[i - 1][j - 1] + matrix[i - 1][j - 1])
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return (self.pre[row2 + 1][col2 + 1] - self.pre[row1][col2 + 1]
- self.pre[row2 + 1][col1] + self.pre[row1][col1])
这里有个值得说的坑：Python 里建二维数组千万别用 [[0] * (n + 1)] * (m + 1)，这种写法会让每一行都指向同一个列表对象，改一个元素整列都变。正确做法是用列表推导式，像我上面那样 [[0] * (n + 1) for _ in range(m + 1)]，每次循环生成一个独立的新列表。
3.3 复杂度分析与时空权衡
初始化阶段遍历矩阵一次，时间复杂度 O(m×n)，空间复杂度 O(m×n)。查询阶段是常数次数组访问，时间复杂度 O(1)。
这个“牺牲预处理换查询速度”的策略，跟缓存索引的本质是一样的。如果查询次数为 q，暴力解的总复杂度是 O(q×m×n)，而前缀和解法总复杂度是 O(m×n + q)。当 q 很大时，后者优势是压倒性的。
空间上看似多了一个 m×n 的表，但每个元素都是整数，对常见矩阵规模来说完全可接受。如果矩阵特别大、内存吃紧，有两个优化方向：一是检查值域是否允许用更紧凑的类型存 pre（例如 int 换成 int32_t 或 short）；二是如果查询模式特殊，可以用行前缀和做折中，后面第五节会提到。
4. 常见问题与排查技巧实录
4.1 Bug 一：下标偏移错位
二维前缀和最经典的 bug 是查询时下标写错。我见过不下十次类似的代码：sumRegion 返回的是 pre[row2][col2] - pre[row1][col2] - pre[row2][col1] + pre[row1][col1]，也就是把 pre 的每一位直接当成“到下标 (i,j) 的和”，而不是“前 i+1 行、前 j+1 列的和”。
这种写法在小矩阵上经常能碰巧通过部分测试，但一旦 row1=0 或 col1=0 就会出错，因为 pre[0][0] 的含义是“到 (0,0) 的和”还是“前 0 行前 0 列的和”会被搞混。要避免这个问题，牢记一条：pre 表的 i 和 j 是“行数和列数”，不是下标。凡是矩阵下标，都要加 1 才能映射到 pre 表。
4.2 Bug 二：空矩阵与非法输入
如果矩阵是空的（m = 0），构造函数里如果先取 matrix[0].size() 就会越界。我的习惯是先判 m，再取 n。如果面试时要求处理更健壮的输入，比如 row1 > row2 或 col1 > col2，可以在查询入口做一次交换或直接判断，不过题目通常已经保证了输入合法。
还有一类边界情况是 n = 0，也就是矩阵没有任何列。虽然题目一般不会给这种输入，但防御性编码可以加一个判断：如果 m == 0 || n == 0，直接让 pre 为空表，查询恒返回 0。
4.3 Bug 三：类型溢出
矩阵元素和 pre 表都用 int 存储，当 m、n 较大且元素值为大整数时，pre[i][j] 的累计值可能超过 int 的范围。题目本身的数值范围通常不会让你溢出，但真实业务里，比如统计千万级用户的消费金额，int 很容易爆。
保守的做法是把 pre 声明成 vector<vector<long long>>，查询返回类型也改成 long long。虽然空间占用翻倍，但换来的是稳定可靠。我自己的习惯是遇到和值可能累加的场景，一律用 long long，宁可多占内存也不在算错之后返工。
4.4 排查技巧：用手画表代替脑内推导
如果你写完代码测试不通过，别急着乱打印日志。拿出纸笔，画一个 3×3 的矩阵，手工算出 pre 表的每一个值，再用同样的数据手动执行 sumRegion，把你算出来的结果和程序输出对比，很快就能定位到是构造公式写错还是查询公式写错。
这个方法听起来土，但对二维前缀和这类“下标别扭”的算法尤其有效。我在公司带新人的时候，让他们遇到这种问题先手推一遍，普遍比对着调试器猜浪费的时间少得多。
5. 扩展与心得：前缀和不止这一道题
5.1 从不可变到可变：什么时候该换方案
前面反复强调“矩阵不可变”是题眼。如果题目改成“矩阵可变”，即支持单点更新和区域查询，静态前缀和就不好使了。单点更新 matrix[i][j] 后，所有满足 i' > i 且 j' > j 的 pre[i'][j'] 都要改，最坏情况要更新整个右下角区域，复杂度 O(m×n)。
针对可变矩阵，业界常用二维树状数组（Binary Indexed Tree），单点更新 O(log m × log n)，区域查询也是这个复杂度；也可以用二维线段树，功能更强但代码量更大。这类题目在面试中出现频率不低，但前提是先掌握静态前缀和，因为树状数组维护的也是前缀和的变体。
5.2 行前缀和的折中方案
如果内存真的紧张到没法存 m×n 的二维前缀表，还有一个折中思路：只对每一行做一维前缀和。查询 [row1, col1] 到 [row2, col2] 时，遍历从 row1 到 row2 的每一行，用一维前缀和 O(1) 求该行在 [col1, col2] 的和，然后累加各行结果。
这种方案的空间是 O(m×n) 降为 O(m×n)——严格说行前缀和的空间还是 O(m×n)，因为每一行的前缀和后缀数组长度也是 n。真正的空间优化需要更精巧的块状分解或平方分解策略，但在实际工程里，二维前缀表的空间消耗通常不会是瓶颈。
5.3 前缀和还能解决哪些变体题
二维前缀和后继的经典变体包括“和为某个目标值的子矩阵数量”，做法是在枚举上下边界的同时，对列前缀和做哈希表统计；还有“最大子矩阵和”，把二维问题通过枚举行边界压缩成一维最大子数组和。这些题目本质都是把二维问题通过某种压缩手段降维，然后复用一维技巧。
日常开发里，滑动窗口统计、图像积分图（Integral Image）和前缀和是同一种思想的不同名字。图像处理中的积分图就是二维前缀和，它能让任意矩形区域的像素求和 O(1) 完成，在人脸识别、图像滤波里是基础操作。所以别觉得算法题跟工程脱节，你现在刷的这道题，本质上就是图像算法工程师每天都在用的工具。我个人在实际操作中的体会是，遇到“静态数据 + 高频区间查询”的组合，首先要想到的往往就是前缀和。与其反复暴力累加，不如一次性把钱花在预处理上，之后每一次查询都变成几次数组访问。这个思路放在这道矩阵题里是答案，放在真实业务里同样是最优解之一。最后再分享一个小技巧：写二维前缀和时，一定要在代码注释里标清楚 pre[i][j] 的含义——前 i 行前 j 列的和。注释写明白了，一个月后回来看代码，你还能立刻想起来下标为什么都要加一，而不是对着公式翻来覆去地猜。