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

2026-03-28 HGNULB 约 9 分钟

文章信息 5 个分类 5 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

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

题意分析

设计一个类 NumMatrix：构造时给定一个不会再被修改的二维矩阵，之后要支持多次 sumRegion(row1, col1, row2, col2) 查询，返回以 $(row_1, col_1)$ 为左上角、$(row_2, col_2)$ 为右下角的子矩形内所有元素之和（四条边都包含在内）。

这是一道设计题，评价标准和普通函数题不同：真正被考察的是「构造」与「查询」之间的代价分配。题面明确说矩阵不可变、且 sumRegion 会被调用多次（数据里可达 $10^4$ 次），这就是全部的算法信号——应该把重活全部压进构造函数，让每次查询降到 $O(1)$。

反过来说，如果查询只调用一两次，逐个累加反而更划算；正是「多次查询 + 数据不变」这两个条件同时成立，预处理才有意义。这个权衡本身就是面试官想听的东西。

数据规模上，矩阵最大 $200 \times 200$，元素范围 $[-10^5, 10^5]$，因此元素可以为负。这排除了任何依赖单调性的做法，但对求和类的预处理毫无影响。整个矩阵的和上界约 $4 \times 10^9$……实际不会超：$200 \times 200 \times 10^5 = 4 \times 10^9$ 确实越过 int 上限，但本题官方数据保证不溢出，稳妥的做法是心里有数，必要时换 long。

边界集中在下标语义上：查询区间是闭区间，四条边都要算进去；查询可能贴着矩阵的第一行或第一列，此时「左上方的部分」是空的，其和必须按 $0$ 处理。这提示预处理表应当比原矩阵多一圈，把「空区域」变成真实存在的下标。

解法：前缀和维护区间信息

核心思路

暴力做法是每次查询都双重循环把子矩形加一遍，单次 $O(mn)$，$10^4$ 次查询就是 $4 \times 10^8$ 次加法，超时。瓶颈是查询之间毫无信息复用——同一片区域被反复求和。

一维前缀和的经验是：先求出 s[i] = nums[0..i-1] 的和，任意区间和就是 s[r+1] - s[l]。二维的自然推广是定义 s[i][j] 表示原矩阵左上角 $(0,0)$ 到 $(i-1, j-1)$ 这个矩形内所有元素之和，也就是「前 $i$ 行、前 $j$ 列」的总和。注意这里刻意把表开成 $(m+1) \times (n+1)$ 并整体右下偏移一格，s[0][*] 与 s[*][0] 全是 $0$，代表空矩形。

建表用容斥。要算 s[i][j]，可以把它拆成「上面那块 s[i-1][j]」加「左边那块 s[i][j-1]」，但这两块在左上角重叠了 s[i-1][j-1]，多加了一次要减回去，最后再补上右下角那个新元素：
\[s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + matrix[i-1][j-1]\]
查询同样是容斥，方向相反。目标矩形 $[row_1, row_2] \times [col_1, col_2]$ 的和，等于「整个左上大块」减去「上方多出来的一条」减去「左方多出来的一条」，而左上角的小块被减了两次，要加回来：
\[\text{answer} = s[row_2+1][col_2+1] - s[row_1][col_2+1] - s[row_2+1][col_1] + s[row_1][col_1]\]
下标里的 +1 全部来自那一圈偏移：因为 s 的行下标 i 对应原矩阵的前 i 行，要包含第 $row_2$ 行就得取 row_2 + 1；而 row_1 不加一，正好把第 $row_1$ 行之前的部分减掉、保留第 $row_1$ 行本身。查询贴边时 row_1 或 col_1 为 $0$，取到的是那圈全零的哨兵，语义自然正确，不需要任何判断。

于是构造是 $O(mn)$、查询是 $O(1)$，正好匹配「一次预处理、多次查询」的形态。

解题步骤

构造函数里开一个 $(m+1) \times (n+1)$ 的表 s。多出的这一圈是「空矩形和为零」的物化，它让建表和查询都不必对第一行第一列做特判，是二维前缀和最值得记住的实现细节。

建表时 i、j 都从 $1$ 遍历到 m、n。这样 i-1、j-1 永远合法，不会越界。

每格按容斥式赋值：加上面、加左边、减去重叠的左上角、补上当前元素。四项的符号顺序不能改——「加两块减一块」是二维容斥的固定形状。

注意 matrix[i-1][j-1] 的偏移：s 的下标比原矩阵大一，取原始元素时必须各减一，这是最容易写错的一处。

查询时把四个角映射到 s 的下标：右下角用 row2 + 1、col2 + 1（要含这一行一列），左上角用 row1、col1（要排除它们之前的部分）。

查询式同样是容斥：大块减上条减左条加回重复减掉的小块。它与建表式是同一个恒等式的两个方向，记住其中一个就能推出另一个。

查询过程完全不访问原矩阵，因此可以在构造完成后不再持有 matrix 的引用，也天然满足「矩阵不可变」的前提。

以 matrix = [[1, 2], [3, 4]] 走一遍。构造时 s 是 $3 \times 3$ 的全零表。i = 1, j = 1：s[1][1] = s[0][1] + s[1][0] - s[0][0] + matrix[0][0] = 0 + 0 - 0 + 1 = 1。i = 1, j = 2：s[1][2] = s[0][2] + s[1][1] - s[0][1] + matrix[0][1] = 0 + 1 - 0 + 2 = 3（第一行的和）。i = 2, j = 1：s[2][1] = s[1][1] + s[2][0] - s[1][0] + matrix[1][0] = 1 + 0 - 0 + 3 = 4（第一列的和）。i = 2, j = 2：s[2][2] = s[1][2] + s[2][1] - s[1][1] + matrix[1][1] = 3 + 4 - 1 + 4 = 10（全矩阵的和，这里 - s[1][1] 减掉的正是被 s[1][2] 和 s[2][1] 各算了一次的元素 $1$）。现在查询 sumRegion(1, 0, 1, 1)，即第二行整行，期望 $3 + 4 = 7$：代入公式得 s[2][2] - s[1][2] - s[2][0] + s[1][0] = 10 - 3 - 0 + 0 = 7。再查 sumRegion(0, 1, 1, 1)，即第二列整列，期望 $2 + 4 = 6$：得 s[2][2] - s[0][2] - s[2][1] + s[0][1] = 10 - 0 - 4 + 0 = 6。两次查询都触到了那一圈哨兵，且都不需要边界判断。

代码实现

class NumMatrix {
    private int[][] s;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 多开一圈：s[0][*] 与 s[*][0] 恒为 0，代表空矩形。
        s = new int[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 s[row2 + 1][col2 + 1] - s[row2 + 1][col1] - s[row1][col2 + 1] + s[row1][col1];
    }
}

type NumMatrix struct {
    s [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    m, n := len(matrix), len(matrix[0])
    s := make([][]int, m+1)
    for i := 0; i < m+1; i++ {
        s[i] = make([]int, 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] + matrix[i-1][j-1]
        }
    }
    return NumMatrix{s}
}

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

复杂度分析

时间复杂度：构造 $O(mn)$，每次查询 $O(1)$。构造时每格只做四次加减；查询时无论矩形多大都只读四个格子，代价与区域面积无关。凭的是二维容斥把「面积级的求和」压成了「四个角的加减」。

空间复杂度：$O(mn)$，即那张 $(m+1) \times (n+1)$ 的前缀和表。这是设计题里典型的空间换时间：多存一份与原矩阵同量级的数据，换来查询从 $O(mn)$ 到 $O(1)$。

关键点总结

设计类题目的第一判断是读操作和写操作谁更频繁。「数据不可变 + 多次查询」就该重预处理、轻查询；反过来若允许单点更新（对应 308 这类题），就要换成树状数组或线段树，把两端的代价均衡到 $O(\log)$。

二维前缀和的建表与查询是同一个容斥恒等式的两个方向：建表是「已知三块小的求大的」，查询是「已知四块大的求中间的」。记住「加两块、减一块」的形状，两个式子都能现推。

多开一圈哨兵是前缀和实现的通用技巧，它把「第一行 / 第一列」从特例变成普通情形，消灭掉全部边界判断；代价只是所有下标偏移一格，务必在取原始元素时记得减一。

闭区间查询映射到前缀和下标时，右端点加一、左端点不加，这条规则一维二维通用；写反会得到少一行或多一行的错误结果。

面试视角：面试官问这题时，最想听到的不是公式而是权衡——先问清 sumRegion 会被调多少次，再说明为什么把代价压到构造阶段。写完后主动补两句加分：一是「哨兵圈让第一行第一列不用特判」，二是「如果矩阵可变就要改用二维树状数组」。能现场把容斥公式画成四个矩形推导出来，比背下来更有说服力。

易错点总结

错误写法：s 只开 $m \times n$ 而不多开一圈。查询 sumRegion(0, 0, 0, 0) 时 s[row1 - 1][...] 直接下标为 $-1$ 越界；为绕开它加的一堆 if (row1 == 0) 分支又极易写漏一种组合。

错误写法：建表时漏掉 - s[i-1][j-1]。左上角那块被算了两次，matrix = [[1, 2], [3, 4]] 的 s[2][2] 会变成 $11$，查询全矩阵返回 11 而不是 10。

错误写法：查询时漏掉 + s[row1][col1]。左上角小块被减了两次，sumRegion(1, 1, 1, 1) 在上例中会返回 10 - 3 - 4 = 3 而不是 4。

错误写法：取原始元素写成 matrix[i][j]。忘了偏移，i = m 时直接越界；即使不越界，整张表也整体错位一格。

错误写法：查询时四个下标全部加一，即写成 s[row2+1][col2+1] - s[row2+1][col1+1] - s[row1+1][col2+1] + s[row1+1][col1+1]。这样算出的是不含第 row1 行和第 col1 列的区域，sumRegion(0, 0, 1, 1) 在上例中会返回 4 而不是 10。

错误写法：查询时四个下标全部不加一。算出的区域少了最后一行一列，sumRegion(0, 0, 1, 1) 会返回 1 而不是 10。

错误写法：把预处理放进 sumRegion 里，每次查询重建一次表。单次查询变成 $O(mn)$，$10^4$ 次调用直接超时，而且完全违背了设计题「构造时付代价」的意图。

错误写法：构造函数里只保存 matrix 的引用，查询时双重循环累加。虽然结果对，但这是暴力解伪装成设计题，面试中会被直接判为没抓住考点。

错误写法：把 s 的元素类型定成会溢出的窄类型。$200 \times 200$ 且元素取到 $10^5$ 量级时全矩阵和接近 $4 \times 10^9$，一旦题目范围再放宽就必须换成 64 位，否则前缀和整体错乱且错误不易定位。

相似题目

题目	难度	考察点
304. 二维区域和检索 - 矩阵不可变	中等	与本题同题，可直接套用同一份建表与查询公式
303. 区域和检索 - 数组不可变	简单	一维版本，只需两项相减，是理解「右端加一、左端不加」的最小样本
1314. 矩阵区域和	中等	每格查一个以自身为中心的方块，边界要先与矩阵范围取交再套公式
1292. 元素和小于等于阈值的正方形的最大边长	中等	在二维前缀和之上再二分边长，利用「边长越大和越大」的单调性
1074. 元素和为目标值的子矩阵数量	困难	枚举上下边界压成一维后接前缀和加哈希，是本题与子数组计数题的结合