二维区域和检索 - 矩阵不可变 图解题解
这道题到底在问什么
- 输入
- matrix = [[3,1,2],[2,4,1],[1,0,3]]
- 输出
- sumRegion(1,1,2,2) = 4+1+0+3 = 8
最优解：一步一步想明白
- 3记住两件事：填表用「上 + 左 − 左上 + 本格」，查询用「大块 − 上 − 左 + 左上角」。下面一格一格演给你看。
- 4先准备一张 4×4 的前缀表 pre，比 3×3 的原矩阵多出第 0 行和第 0 列。这一圈待会儿全部填 0。
- 5把边界这一圈先填成 0。它们代表「空矩形」，里面没有数，和自然是 0。接下来只填中间这块真正的格子。
- 6要填 pre[1][1]（橙框）。蓝色三格是它依赖的：正上 0、正左 0、左上 0；再加上原矩阵这一格的值 3。
- 7算出 0 + 0 − 0 + 3 = 3，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
- 8要填 pre[1][2]（橙框）。蓝色三格是它依赖的：正上 0、正左 3、左上 0；再加上原矩阵这一格的值 1。
- 9算出 0 + 3 − 0 + 1 = 4，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
- 10要填 pre[1][3]（橙框）。蓝色三格是它依赖的：正上 0、正左 4、左上 0；再加上原矩阵这一格的值 2。
- 11算出 0 + 4 − 0 + 2 = 6，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
- 12要填 pre[2][1]（橙框）。蓝色三格是它依赖的：正上 3、正左 0、左上 0；再加上原矩阵这一格的值 2。
- 13算出 3 + 0 − 0 + 2 = 5，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
- 14要填 pre[2][2]（橙框）。蓝色三格是它依赖的：正上 4、正左 5、左上 3；再加上原矩阵这一格的值 4。
- 15算出 4 + 5 − 3 + 4 = 10，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
- 16要填 pre[2][3]（橙框）。蓝色三格是它依赖的：正上 6、正左 10、左上 4；再加上原矩阵这一格的值 1。
- 17算出 6 + 10 − 4 + 1 = 13，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
- 18要填 pre[3][1]（橙框）。蓝色三格是它依赖的：正上 5、正左 0、左上 0；再加上原矩阵这一格的值 1。
- 19算出 5 + 0 − 0 + 1 = 6，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
- 20要填 pre[3][2]（橙框）。蓝色三格是它依赖的：正上 10、正左 6、左上 5；再加上原矩阵这一格的值 0。
- 21算出 10 + 6 − 5 + 0 = 11，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
- 22要填 pre[3][3]（橙框）。蓝色三格是它依赖的：正上 13、正左 11、左上 10；再加上原矩阵这一格的值 3。
- 23算出 13 + 11 − 10 + 3 = 17，填进橙框。左上那块被上、左各数了一次，所以要减一次补回来。
- 24整张前缀表建好了。最右下角 pre[3][3]=17，正好是整个矩阵九个数的总和。之后所有查询都基于这张表。
- 25现在查询左上 (1,1) 到右下 (2,2) 这块区域的和。第一步：取右下角大块 pre[3][3]=17，它是从最左上一直到这块右下角的总和（包含了多余部分）。
- 26大块里把目标区域上面那几行也算进去了。减掉 pre[1][3]=6，把上方多余的部分去掉。
- 27同样，大块里目标区域左边那几列也被算进去了。再减掉 pre[3][1]=6，去掉左方多余的部分。
- 28左上角那一小块被上、左两次各减掉了一次，多减了，要加回 pre[1][1]=3。最终 17−6−6+3=8。
- 29答案是 8。回到原矩阵数一遍：那块四个数 4、1、0、3 加起来正好是 8，对上了。整个查询只用了 4 次加减。
⚠️ 容易写错的地方
✗ 错：填表忘了「减左上」
✓ 对：pre[i][j] = 上 + 左 − 左上 + 本格
上、左两块在左上角那块上重叠了一次，不减会把左上区域多加一遍
✗ 错：查询时下标没 +1
✓ 对：用 pre[r2+1][c2+1] 等，行列都要 +1
pre 比原矩阵多一圈边界，原矩阵的 (r,c) 对应 pre 的 (r+1,c+1)
✗ 错：查询忘了「加回左上角」
✓ 对：最后 + pre[r1][c1]
上方块、左方块都把左上那块各减了一次，多减一次必须补回来
完整代码（Python / C++ / Java）
Python
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]C++
class NumMatrix {
vector<vector<int>> pre;
public:
NumMatrix(vector<vector<int>>& a) {
int m = a.size(), n = a[0].size();
pre.assign(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] + a[i-1][j-1];
}
int sumRegion(int r1,int c1,int r2,int c2){
return pre[r2+1][c2+1]-pre[r1][c2+1]-pre[r2+1][c1]+pre[r1][c1];
}
};Java
class NumMatrix {
private int[][] pre;
public NumMatrix(int[][] a) {
int m = a.length, n = a[0].length;
pre = new int[m+1][n+1];
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] + a[i-1][j-1];
}
public int sumRegion(int r1,int c1,int r2,int c2){
return pre[r2+1][c2+1]-pre[r1][c2+1]-pre[r2+1][c1]+pre[r1][c1];
}
}复杂度
预处理
O(m·n)
填前缀表，每个格子算一次，共 m·n 个格子
单次查询
O(1)
只取 4 个前缀值做加减，和查询区域大小无关
空间
O(m·n)
存一张 (m+1)·(n+1) 的前缀表
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二维区域和检索 - 矩阵不可变 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
前缀表为什么要多出第 0 行和第 0 列？+
为了让边界统一好算。有了这圈 0，填 pre[1][j] 时直接引用 pre[0][j]=0，不用对第一行第一列写特殊判断；查询时引用 pre[r1][...]、pre[...][c1] 也不会越界。
如果矩阵会被频繁修改怎么办？+
前缀和表一改就要大面积重建，不再划算。此时改用二维树状数组（Fenwick）或二维线段树，单点更新和区域查询都是 O(log m · log n)。
一维的「区域和检索」和这题什么关系？+
一维（LC303）是这题的特例：前缀和数组 pre[i]=前 i 个数之和，查询 sum(l,r)=pre[r+1]−pre[l]。二维只是在行、列两个方向各做一次前缀和，并用容斥处理重叠。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 二维区域和检索 - 矩阵不可变 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。