LeetCode LCR 013. 二维区域和检索 - 矩阵不可变
题目描述
题意分析
构造时给定一个不会再修改的矩阵，之后多次查询指定子矩形内的元素总和。查询由左上角
(row1, col1)和右下角(row2, col2)给出，四条边上的元素都包含在内。矩阵元素可以为负，查询区域也可能贴着第一行或第一列。数据固定、查询重复，适合先整理所有左上前缀区域的和，让每次查询只做固定次数的加减。
官方题面同时声明
int sumRegion和最大200 × 200、单格绝对值不超过10^5，因此数值范围本身允许区域和达到4 × 10^9，并没有给出“所有结果保证不超过32位”的承诺。下面用64位保存前缀及中间计算，保留题面返回接口；最终转为int只适用于结果在该返回类型范围内的查询。要覆盖这些超出范围的查询，返回类型也必须相应扩大。
解法：二维前缀和
核心思路
[!blue]
定义
s[i][j]为原矩阵前i行、前j列的总和，即覆盖[0, i) × [0, j)。前缀表比原矩阵多一行一列，s[0][*]、s[*][0]表示空区域，初值全部为零。构造
s[i][j]时，上方前缀和左方前缀合起来已经覆盖所需区域的大部分，但左上重叠部分被加了两次，还缺右下角的新元素。因此：
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + matrix[i - 1][j - 1]。查询时从包含右下角的大前缀
s[row2 + 1][col2 + 1]出发，减去查询上方的前缀和左方的前缀。这两个被减区域的左上交集被重复减了一次，所以还要加回s[row1][col1]。由此得到四项查询式：
s[row2 + 1][col2 + 1] - s[row2 + 1][col1] - s[row1][col2 + 1] + s[row1][col1]。右下角加一是为了把闭区间端点包含进来；左上角不加一，减掉的恰好是它之前的部分。查询贴边时会访问那一圈全零前缀，仍适用同一公式。构造与查询都只使用加减，负数不影响容斥；64位前缀使大区域和保持真实值，避免中间表发生32位回绕。
解题步骤
- 创建
(m + 1) × (n + 1)的64位前缀表，保留首行首列为零。- 从前缀下标一开始填表，将上方与左方相加，减去重叠区域，再加对应原元素。
- 查询时读取右下大前缀、上方前缀、左方前缀及重复减掉的左上前缀。
- 按加减公式得到64位区域和，再按保留的题面接口转换返回；返回类型的可表示范围仍需单独满足。
代码实现
class NumMatrix {
private long[][] s;
public NumMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
// 多开一圈：s[0][*] 与 s[*][0] 恒为 0，代表空矩形。
s = new long[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
// 加上面 + 加左边 - 减重叠 + 补当前元素。
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
// 右下角要含自身故 +1，左上角不加一以排除其之前的部分。
return (int) (s[row2 + 1][col2 + 1] - s[row2 + 1][col1] - s[row1][col2 + 1] + s[row1][col1]);
}
}
type NumMatrix struct {
s [][]int64
}
func Constructor(matrix [][]int) NumMatrix {
m, n := len(matrix), len(matrix[0])
s := make([][]int64, m+1)
for i := 0; i < m+1; i++ {
s[i] = make([]int64, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + int64(matrix[i-1][j-1])
}
}
return NumMatrix{s}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
return int(this.s[row2+1][col2+1] - this.s[row2+1][col1] - this.s[row1][col2+1] + this.s[row1][col1])
}
复杂度分析
设矩阵有 $m$ 行、$n$ 列。
- 时间复杂度：构造为 $O(mn)$，每次查询为 $O(1)$，与查询矩形的面积无关。
- 辅助空间复杂度：$O(mn)$，保存二维前缀表，之后查询无需再扫描原矩阵。
关键点总结
[!green]
- 前缀下标表示行列数量，统一使用左闭右开语义。
- 建表减掉重复相加的左上区域，查询加回重复减掉的左上区域。
- 首行首列的零区域统一处理贴边查询。
- 存储类型与返回类型都必须覆盖各自的数值范围，扩大前缀类型不会扩大返回接口的范围。
易错点总结
[!yellow]
- 建表访问原元素时要把前缀下标各减一，不能混用两套下标。
- 查询右下角需要加一，否则会漏掉最后一行或一列。
- 查询减去上方和左方后，必须加回被重复减掉的左上区域。
- 前缀和与容斥中间值可能超出32位，存储和计算都应使用宽整数。
- 最后直接转成窄整数并不会扩大接口的范围，超范围查询仍不能由32位返回值正确表示。
- 本方案用于矩阵不变的场景，修改原数据后旧前缀表不会自动更新。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 303. 区域和检索 - 数组不可变 | 简单 | 把一维前缀差推广到二维矩形，需要四个角做容斥。 |
| 307. 区域和检索 - 数组可修改 | 中等 | 原题存在更新操作，静态前缀和不再适合每次重建，需要树状数组等动态结构。 |