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

约 5 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 微软
标签
数组 矩阵 设计 前缀和

题目描述

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

image-20260928223255781

image-20260928223255783

image-20260928223255784

题意分析

矩阵初始化后不再修改，需要多次查询由左上角 (row1, col1) 和右下角 (row2, col2) 围成的矩形元素和，两个边界都包含在内。

每次重新遍历查询区域会重复计算大量重叠部分。由于矩阵固定，可以先保存从左上角出发的所有前缀矩形和，再用固定次数的加减得到任意查询区域。

解法：二维前缀和

核心思路

[!blue]

定义 prefix[i][j] 为原矩阵前 i 行、前 j 列的元素和，也就是行范围 [0, i)、列范围 [0, j)。因此表的大小是 (m + 1) × (n + 1)，第 0 行或第 0 列表示空矩形，值都为 0。

建表时，把上方前缀 prefix[i - 1][j] 与左方前缀 prefix[i][j - 1] 相加，左上角 prefix[i - 1][j - 1] 被计算了两次，需要减去一次，最后再加入两者都没有包含的当前格 matrix[i - 1][j - 1]。按行列递增计算时，这三个依赖都已经就绪。

查询也使用同样的容斥。先取覆盖到右下角的 prefix[row2 + 1][col2 + 1]，减去目标上方的 prefix[row1][col2 + 1]，再减去左方的 prefix[row2 + 1][col1]。这时左上重叠区域被多减了一次，所以要加回 prefix[row1][col1]。

零行、零列把贴着矩阵边界的查询统一成同一个公式：目标上方或左方不存在区域时，对应前缀值自然为零，无需额外分支。

解题步骤

  1. 构造时创建 m + 1 行、n + 1 列的前缀和表，保留第 0 行与第 0 列为零。
  2. 遍历 i = 1..m、j = 1..n，按照“上方 + 左方 - 左上重叠 + 当前格”计算 prefix[i][j]。
  3. 每次查询把右下角的行、列下标分别加一，得到包含该边界的前缀矩形。
  4. 返回“大矩形 - 上方 - 左方 + 左上重叠”，只读取四个前缀值。

代码实现

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(mn)$，每次查询 $O(1)$。
  • 空间复杂度：$O(mn)$，保存二维前缀和。

关键点总结

[!green]

  • 前缀表的下标表示行列数量，原矩阵的下标表示格子位置，两者相差一。
  • 建表时重叠区域被多加，查询时重叠区域被多减，所以修正符号不同。
  • 一次预处理承担全部遍历成本，矩阵保持不变后，每次查询都是常数时间。

易错点总结

[!yellow]

  • 查询是闭区间，右下角必须加一；左上角用于表示要排除的行列数量，不加一。
  • 查询时漏掉最后加回的左上前缀，会把重叠部分多减一次。
  • 建表时当前格是 matrix[i - 1][j - 1]，不能直接使用前缀表的下标访问原矩阵。
  • Java 代码沿用标准 int 返回接口，适用于查询结果能由 int 表示的情况；若需支持更宽的结果，必须连同前缀表和返回类型一起扩展，仅扩大中间变量不能解决返回范围限制。

相似题目

题目 难度 关联与区别
303. 区域和检索 - 数组不可变 简单 把一维前缀差推广到二维矩形，需要四个角做容斥。
307. 区域和检索 - 数组可修改 中等 原题存在更新操作，静态前缀和不再适合每次重建，需要树状数组等动态结构。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/60478616
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！