304. 二维区域和检索 - 矩阵不可变（Range Sum Query 2D - Immutable）

频次 ★★★ · 难度 🟡 · 高频：美团

题目

二维矩阵不可变，多次查询 (r1,c1)-(r2,c2) 子矩阵和。

思路

二维前缀和：pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + matrix[i][j]。

查询：sum = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]。

代码

class NumMatrix {
    private int[][] pre;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        pre = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + matrix[i][j];
    }
    public int sumRegion(int r1, int c1, int r2, int c2) {
        return pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1];
    }
}

复杂度

• 时间：O(mn) 初始化，O(1) 查询
• 空间：O(mn)

边界条件

• pre 开 (m+1) × (n+1)：第 0 行和第 0 列全为 0，充当哨兵，消灭 r1 == 0 或 c1 == 0 的特判
• 空矩阵：matrix.length == 0 时 matrix[0] 会抛异常，构造函数要先判
• 单行/单列矩阵：容斥公式自然退化，不需要特殊处理
• 溢出：m、n 都大时 pre 的右下角是全矩阵和，int 可能不够

变式

• 303. 区域和检索：一维版本，是本题的降维
• 子矩阵和等于 K 的个数：固定上下边界压成一维，转化为 560. 和为 K 的子数组
• 矩阵可变：二维树状数组或线段树套线段树
• 三维前缀和：容斥项从 4 个变 8 个，符号规律是 (-1)^(维度差)

易错点

• 构造和查询的容斥符号方向相反,是最常见的错。构造是 pre[i][j+1] + pre[i+1][j] - pre[i][j] + matrix[i][j]（减重叠部分），查询是 pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]（减两条边、加回多减的那个角）。记反了不会报错，只会算错。
• 查询里的四个下标都要 +1 偏移，唯独左上角 pre[r1][c1] 不加——因为它取的是 (r1,c1) 之前的部分
• 别把 matrix[i][j] 写成 matrix[i+1][j+1]：pre 有偏移，matrix 没有

面试追问

• 画个图讲清容斥：pre[i][j] 是从原点到 (i-1, j-1) 的矩形和。求任意子矩形时，先拿最大的那块（右下角），减掉上方整条和左方整条——此时左上角那块被减了两次，所以要加回来一次。这就是容斥原理最朴素的两维形态。
• 为什么维度越高越不划算：d 维前缀和的查询要 2^d 项容斥。三维要 8 项，四维 16 项，常数吃掉了 O(1) 的优势。高维稀疏数据一般改用 KD 树或直接扫。
• 和 OLAP 的 cube 是同一件事吗：是。数据仓库的预聚合 cube 就是多维前缀和，GROUP BY 的上卷下钻对应前缀和的容斥查询。它同样只在事实表不变（或按批刷新）时才划算。
• 这题为什么是 🟡 而 303 是 🟢：一维前缀和的差分是减一项，直觉上显然；二维要处理重叠区域，需要容斥。难度的跳跃点不在”前缀和”这个概念，而在”重叠”这个几何事实。

关联题

• 基础：303. 区域和检索、560. 和为 K 的子数组