LeetCode 304. 二维区域和检索 - 矩阵不可变

2022-03-29 HGNULB 约 9 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 304. 二维区域和检索 - 矩阵不可变

题意分析

设计一个类，构造时接收一个不会再修改的二维矩阵，之后支持大量 sumRegion(row1, col1, row2, col2) 查询，返回以 (row1, col1) 为左上角、(row2, col2) 为右下角的闭矩形区域内所有元素之和。

两条约束共同决定了解法形态：矩阵不可变，且查询次数可能高达上万次。不可变意味着预处理的结果永远有效，不需要考虑更新；查询量大意味着必须把单次查询压到常数级，哪怕预处理要付出遍历整个矩阵的代价也划算。这是典型的「一次预处理、多次 $O(1)$ 查询」的设计题。

查询区间是闭区间，四个坐标都包含在内，这一点决定了坐标换算时的加一减一。

元素可能是负数，所以不能用「和随区间增大而单调」之类的性质做剪枝；但前缀和的容斥公式对负数同样成立，不受影响。

边界包括：查询整个矩阵；查询单个格子；row1 或 col1 为 0 时不能出现负下标。

解法：二维前缀和

核心思路

最朴素的实现是每次查询都二重循环把区域内的元素加一遍，单次 $O(m \cdot n)$。矩阵一百乘一百、查询上万次时就是上亿次加法，明显超时。瓶颈在于不同查询的区域大量重叠，同一个元素被反复累加。

一维的情形我们很熟悉：预处理前缀和 pre[i] 表示前 i 个元素之和，则区间和等于 pre[r+1] - pre[l]。二维的自然推广是定义 prefix[i][j] 表示从原矩阵左上角 (0,0) 到 (i-1, j-1) 这个矩形内所有元素之和，也就是「以某点为右下角的前缀矩形和」。

有了这个定义，任意矩形都能用容斥拼出来。目标矩形 = 大前缀矩形 − 上方多余部分 − 左方多余部分 + 左上角被减了两次的部分，写成公式就是：

sumRegion = prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]

最后那一项加回来，是因为左上角那块区域同时属于「上方多余」和「左方多余」，被减了两次，必须补一次。这就是二维容斥原理。

前缀和自身的递推同理：prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1]，上方和左方两块重叠了左上角，先减掉再补上当前格。

由此可以写出维护的不变量：填完 prefix[i][j] 时，它恒等于原矩阵前 i 行前 j 列构成的矩形内所有元素之和。按行从上到下、按列从左到右填表时，公式右侧的三项都已经算好，递推合法。

数组开成 (m+1) × (n+1) 而不是 m × n 是一个关键的工程选择。多出来的第 0 行和第 0 列恒为 0，代表「空矩形和为 0」，于是 row1 = 0 或 col1 = 0 的查询会自然地读到这些 0，不需要任何 if 分支。哨兵行列换来的是零分支的干净代码，这是前缀和题的通用技巧。

解题步骤

构造函数中读出矩阵的行数 m 和列数 n，开 (m+1) × (n+1) 的 prefix 数组，默认全 0。第 0 行第 0 列作为哨兵永不写入，它们代表空区域。

双重循环从 i = 1、j = 1 开始填表。下标从 1 起是为了让 prefix[i-1][*] 与 prefix[*][j-1] 总是合法，不用为第一行第一列写特判。

每格按 上 + 左 - 左上 + 当前元素 递推。注意当前元素是 matrix[i-1][j-1]：prefix 的下标比原矩阵整体偏移了 1，这个偏移必须全程保持一致。

查询时把闭区间的坐标转换到 prefix 坐标系：右下角要加 1（因为闭区间包含 row2、col2），左上角不加（因为要排除第 row1 行和第 col1 列之前的部分，恰好等于 prefix 中下标 row1、col1 的值）。

按容斥公式做一次「加减减加」返回，四次数组访问，常数时间。

以 matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]] 走一遍，查询 sumRegion(2, 1, 4, 3)，期望答案 8。

先看 prefix 表的几个关键值。prefix[2][1] 是前 2 行前 1 列的和，即 3 + 5 = 8。prefix[2][4] 是前 2 行前 4 列的和，即第 0 行的 3+0+1+4 = 8 加第 1 行的 5+6+3+2 = 16，合计 24。prefix[5][1] 是前 5 行前 1 列的和，即 3+5+1+4+1 = 14。prefix[5][4] 是前 5 行前 4 列的和：第 0 行 8、第 1 行 16、第 2 行 1+2+0+1 = 4、第 3 行 4+1+0+1 = 6、第 4 行 1+0+3+0 = 4，合计 38。

代入公式：prefix[4+1][3+1] - prefix[2][3+1] - prefix[4+1][1] + prefix[2][1] = 38 - 24 - 14 + 8 = 8。

手工核对目标区域，它是第 2 到 4 行、第 1 到 3 列：第 2 行取 2、0、1 得 3，第 3 行取 1、0、1 得 2，第 4 行取 0、3、0 得 3，总和 8，与公式结果一致。

注意最后那个 + prefix[2][1] = 8 的作用：前两行前一列这块区域在减去「上方 24」和「左方 14」时各被减了一次，不补回来结果会变成 0，正好差了这块的 8。

代码实现

class NumMatrix {
    private final int[][] prefix;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        prefix = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = prefix[i - 1][j]
                        + prefix[i][j - 1]
                        - prefix[i - 1][j - 1]
                        + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return prefix[row2 + 1][col2 + 1]
                - prefix[row1][col2 + 1]
                - prefix[row2 + 1][col1]
                + prefix[row1][col1];
    }
}

type NumMatrix struct {
    prefix [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    m, n := len(matrix), len(matrix[0])
    prefix := make([][]int, m+1)
    for i := range prefix {
        prefix[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            prefix[i][j] = prefix[i-1][j] +
                prefix[i][j-1] -
                prefix[i-1][j-1] +
                matrix[i-1][j-1]
        }
    }

    return NumMatrix{prefix: prefix}
}

func (m *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    return m.prefix[row2+1][col2+1] -
        m.prefix[row1][col2+1] -
        m.prefix[row2+1][col1] +
        m.prefix[row1][col1]
}

复杂度分析

时间复杂度：构造函数 $O(m \cdot n)$，每格只做常数次加减；单次查询 $O(1)$，固定四次数组访问，与区域大小无关。

空间复杂度：$O(m \cdot n)$，前缀和表比原矩阵多一行一列；这是用空间换查询时间的典型交易，矩阵不可变让这笔投入一次付清、无限复用。

关键点总结

「不可变数据 + 大量区间查询」是前缀和的标准信号，把代价从「每次查询 $O(区域大小)$」搬到「一次预处理 $O(总规模)$」，查询降为常数。

二维前缀和的两个公式（建表与查询）都源自容斥：上加左减左上，重叠部分被减两次就要补一次，理解这一点就不必死记符号。

多开一行一列的哨兵是这类题的必备技巧，它把「下标为 0 时不能减一」的边界分支彻底消除，代码更短也更不易错。

下标偏移必须全程一致：prefix 用 1 基、matrix 用 0 基，写代码时把「prefix[i][j] 对应 matrix[i-1][j-1]」写在注释或心里，任何一处漏掉减一都会整体错位。

面试视角：面试官会顺着问三层——如果矩阵会被修改怎么办（前缀和失效，改用二维树状数组或线段树，查询与更新都是 $O(\log m \log n)$）；如果只查询固定大小的窗口呢（可以只维护一维前缀和逐行累加）；数值范围大会不会溢出（元素上万乘上格子数可能超过 int，要评估是否用 long）。

易错点总结

错误写法：prefix 数组只开 m × n 并在查询里写 prefix[row1-1][...] → 用例 sumRegion(0, 0, 1, 1)，row1 为 0 时下标为 -1，Java 抛越界异常、Go 直接 panic。

错误写法：容斥公式漏掉最后一项 + prefix[row1][col1] → 用例矩阵 [[1,2],[3,4]] 查询 sumRegion(1, 1, 1, 1)，得到 10 - 3 - 4 = 3，正确答案是 4。

错误写法：把最后一项写成减号 - prefix[row1][col1] → 用例同上得到 10 - 3 - 4 - 1 = 2，比正确答案少了两倍的左上角。

错误写法：查询时右下角忘记加一，写成 prefix[row2][col2] → 用例矩阵 [[1,2],[3,4]] 查询 sumRegion(0, 0, 1, 1)，得到 prefix[1][1] = 1，正确答案是 10。

错误写法：查询时左上角也加了一，写成 prefix[row1+1][col2+1] → 用例 sumRegion(0, 0, 1, 1)，把第 0 行整行错误地减掉，返回 7 而不是 10。

错误写法：建表时把当前元素写成 matrix[i][j] 而不是 matrix[i-1][j-1] → 用例矩阵 [[1,2],[3,4]]，i、j 取到 m、n 时直接越界。

错误写法：建表递推漏掉 - prefix[i-1][j-1] → 用例矩阵 [[1,2],[3,4]]，prefix[2][2] 被算成 4 + 3 + 4 = 11，正确值是 10，之后所有查询都会偏大。

错误写法：把预处理放在 sumRegion 里每次重建 → 用例是上万次查询，每次都要 $O(mn)$ 建表，退化回暴力甚至更慢，直接超时。

错误写法：用 matrix[0].length 之外的方式取列数，比如误用 matrix.length → 用例矩阵 [[1,2,3]]，m 和 n 都取 1，表只建了一格，查询第 2 列时越界。

错误写法：Go 里只写 prefix := make([][]int, m+1) 而忘记给每一行 make → 用例任意，所有内层切片为 nil，写入时立刻 panic。

错误写法：Java 里把 prefix 声明为局部变量而非成员字段 → 构造函数结束后表被回收，sumRegion 里根本访问不到，编译期就会报错或被迫每次重建。

错误写法：认为查询区间是半开的，把 col2 理解成不包含 → 用例矩阵 [[1,2],[3,4]] 查询 sumRegion(0, 0, 0, 1)，返回 1 而不是 3。

相似题目

题目	难度	考察点
303. 区域和检索 - 数组不可变	简单	一维版本，是理解哨兵位与下标偏移的最佳起点
LCR 013. 二维区域和检索 - 矩阵不可变	中等	完全同题的中文版，可用来对照容斥公式的符号
1314. 矩阵区域和	中等	每格都要查一次固定半径的窗口，边界需要做坐标钳制
1292. 元素和小于等于阈值的正方形的最大边长	中等	在前缀和之上再套一层对边长的二分或递增枚举
560. 和为 K 的子数组	中等	一维前缀和配哈希表统计，考察「前缀差等于 K」的转化
1074. 元素和为目标值的子矩阵数量	困难	把行区间压成一维后套 560 的哈希做法，是二维前缀和的进阶用法
363. 矩形区域不超过 K 的最大数值和	困难	需要在压缩后的一维前缀和上用有序集合找最接近 K 的上界