题目描述
思路解析动画文字版
和 303 一样，题目强调多个查询，就是在提醒你把重复计算提前到初始化阶段。
多开一行一列 0 哨兵后，row1=0 或 col1=0 的查询也能套同一个公式。
初始化：第 0 行和第 0 列都是 0：哨兵 0 让公式不用处理边界特判。此时还没有填入任何 matrix 值；表格坐标是 pre 的坐标，比 matrix 坐标都大 1。
填 pre[1][1]：加入 matrix[0][0]=3：pre[1][1] 表示只覆盖 matrix[0][0] 的小矩形，所以结果是 3。
填 pre[1][2]：第一行继续向右：第一行第二个数是 0，所以前缀和仍然是 3。
填 pre[1][3]：覆盖 matrix 第一行前三列：现在 pre[1][3] 覆盖 matrix[0][0..2]，也就是 3+0+1=4。
填 pre[2][1]：第二行第一列：pre[2][1] 覆盖 matrix 前两行第一列：3+5=8。
填 pre[2][2]：第一次出现重叠，要减左上：上方矩形和左方矩形都包含左上角那块 3，所以要减掉一次 pre[1][1]，这就是二维前缀和最关键的一步。
继续填 pre[2][3]：同一个容斥公式：继续往右填，依然是“当前值 + 上 + 左 - 左上”。只要每一格都维护这个不变量，整张表就会正确。
填到 pre[3][3]：看见更大的矩形：pre[3][3] 覆盖 matrix 左上 3x3 区域。matrix[2][2] 虽然是 0，也要完整套公式。
按同一公式填完整张 pre 表：后面的格子没有新规则，都是同一个“当前 + 上 + 左 - 左上”公式。初始化结束后，查询只看四个角。
查询 sumRegion(2,1,4,3)：四个角分别是：右下 pre[5][4]，上方 pre[2][4]，左方 pre[5][1]，左上重叠 pre[2][1]。pre 坐标比 matrix 坐标多 1。
查询 sumRegion(1,1,2,2)：右下 pre[3][3] 减上方 pre[1][3]，再减左方 pre[3][1]，最后把左上重叠 pre[1][1] 加回来。
查询 sumRegion(1,2,2,4)：右下 pre[3][5]、上方 pre[1][5]、左方 pre[3][2]、左上重叠 pre[1][2] 四个角一带入，就得到 12。
只要记住“多算的减掉，少算的补回”，二维公式就不会变成硬背。
参考代码
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(m): for j in range(n): self.pre[i + 1][j + 1] = ( matrix[i][j] + self.pre[i][j + 1] + self.pre[i + 1][j] - self.pre[i][j] ) def sumRegion(self, row1, col1, row2, col2): return ( self.pre[row2 + 1][col2 + 1] - self.pre[row1][col2 + 1] - self.pre[row2 + 1][col1] + self.pre[row1][col1] )复杂度
- 初始化时间：O(mn)，双重循环填完整张 pre 表。
- 单次查询时间：O(1)，sumRegion 只访问四个 pre 单元格。
- 空间复杂度：O(mn)，额外保存 (m+1) x (n+1) 的二维前缀和表。
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
和为 K 的子数组
LeetCode 560 · 中等 · 沿着 前缀和套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题