题目描述
思路解析动画文字版
记住两件事：填表用「上 + 左 − 左上 + 本格」，查询用「大块 − 上 − 左 + 左上角」。下面一格一格演给你看。
先准备一张 4×4 的前缀表 pre，比 3×3 的原矩阵多出第 0 行和第 0 列。这一圈待会儿全部填 0。
把边界这一圈先填成 0。它们代表「空矩形」，里面没有数，和自然是 0。接下来只填中间这块真正的格子。
要填 pre[1][1]（橙框）。蓝色三格是它依赖的：正上 0、正左 0、左上 0；再加上原矩阵这一格的值 3。
算出 0 + 0 − 0 + 3 = 3，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
要填 pre[1][2]（橙框）。蓝色三格是它依赖的：正上 0、正左 3、左上 0；再加上原矩阵这一格的值 1。
算出 0 + 3 − 0 + 1 = 4，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
要填 pre[1][3]（橙框）。蓝色三格是它依赖的：正上 0、正左 4、左上 0；再加上原矩阵这一格的值 2。
算出 0 + 4 − 0 + 2 = 6，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
要填 pre[2][1]（橙框）。蓝色三格是它依赖的：正上 3、正左 0、左上 0；再加上原矩阵这一格的值 2。
算出 3 + 0 − 0 + 2 = 5，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
要填 pre[2][2]（橙框）。蓝色三格是它依赖的：正上 4、正左 5、左上 3；再加上原矩阵这一格的值 4。
算出 4 + 5 − 3 + 4 = 10，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
要填 pre[2][3]（橙框）。蓝色三格是它依赖的：正上 6、正左 10、左上 4；再加上原矩阵这一格的值 1。
算出 6 + 10 − 4 + 1 = 13，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
要填 pre[3][1]（橙框）。蓝色三格是它依赖的：正上 5、正左 0、左上 0；再加上原矩阵这一格的值 1。
算出 5 + 0 − 0 + 1 = 6，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
要填 pre[3][2]（橙框）。蓝色三格是它依赖的：正上 10、正左 6、左上 5；再加上原矩阵这一格的值 0。
算出 10 + 6 − 5 + 0 = 11，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
要填 pre[3][3]（橙框）。蓝色三格是它依赖的：正上 13、正左 11、左上 10；再加上原矩阵这一格的值 3。
算出 13 + 11 − 10 + 3 = 17，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
整张前缀表建好了。最右下角 pre[3][3]=17，正好是整个矩阵九个数的总和。之后所有查询都基于这张表。
现在查询左上 (1,1) 到右下 (2,2) 这块区域的和。第一步：取右下角大块 pre[3][3]=17，它是从最左上一直到这块右下角的总和（包含了多余部分）。
大块里把目标区域上面那几行也算进去了。减掉 pre[1][3]=6，把上方多余的部分去掉。
同样，大块里目标区域左边那几列也被算进去了。再减掉 pre[3][1]=6，去掉左方多余的部分。
左上角那一小块被上、左两次各减掉了一次，多减了，要加回 pre[1][1]=3。最终 17−6−6+3=8。
答案是 8。回到原矩阵数一遍：那块四个数 4、1、0、3 加起来正好是 8，对上了。整个查询只用了 4 次加减。
三个高频追问：多一圈 0 的作用、矩阵可变时的替代方案、以及和一维前缀和的联系。
参考代码
class NumMatrix: def __init__(self, matrix): m, n = len(matrix), 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, r1, c1, r2, c2): p = self.pre return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]复杂度
- 预处理：O(m·n)，填前缀表，每个格子算一次，共 m·n 个格子
- 单次查询：O(1)，只取 4 个前缀值做加减，和查询区域大小无关
- 空间：O(m·n)，存一张 (m+1)·(n+1) 的前缀表
易错点
面试追问把动画讲成自己的话
追问前缀表为什么要多出第 0 行和第 0 列？
追问如果矩阵会被频繁修改怎么办？
追问一维的「区域和检索」和这题什么关系？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
连续的子数组和
LeetCode 523 · 中等 · 沿着 前缀和套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题