题目

标题和出处

标题：二维区域和检索 - 矩阵不可变

出处：304. 二维区域和检索 - 矩阵不可变

难度

5 级

题目描述

要求

给定一个二维矩阵 $\text{matrix}$，处理以下类型的多个查询:

• 计算以 $\text{(row1, col1)}$ 为左上角、$\text{(row2, col2)}$ 为右下角的子矩阵元素的和。

实现 $\text{NumMatrix}$ 类：

• $\text{NumMatrix(int[] matrix)}$ 使用矩阵 $\text{matrix}$ 初始化对象。
• $\text{int sumRegion(int row1, int col1, int row2, int col2)}$ 返回矩阵 $\text{matrix}$ 中的以 $\text{(row1, col1)}$ 为左上角、$\text{(row2, col2)}$ 为右下角的子矩阵元素的和。

要求 $\text{sumRegion}$ 的时间复杂度是 $\text{O(1)}$。

示例

示例 1：

输入：
$\text{["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]}$
$\text{[[[[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]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]}$
输出：
$\text{[null, 8, 11, 12]}$
解释：
$\text{NumMatrix numMatrix = new NumMatrix([[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]]);}$
$\text{numMatrix.sumRegion(2, 1, 4, 3);}$ // 返回 $\text{8}$（红色矩形框的元素和）
$\text{numMatrix.sumRegion(1, 1, 2, 2);}$ // 返回 $\text{11}$（绿色矩形框的元素和）
$\text{numMatrix.sumRegion(1, 2, 2, 4);}$ // 返回 $\text{12}$（蓝色矩形框的元素和）

数据范围

• $\text{m}=\text{matrix.length}$
• $\text{n}=\text{matrix[i].length}$
• $\text{1}\le \text{m, n}\le \text{200}$
• ${\text{-10}}^{\text{5}}\le \text{matrix[i][j]}\le {\text{10}}^{\text{5}}$
• $\text{0}\le \text{row1}\le \text{row2}<\text{m}$
• $\text{0}\le \text{col1}\le \text{col2}<\text{n}$
• 最多调用 ${\text{10}}^{\text{4}}$ 次 $\text{sumRegion}$ 方法

前言

这道题是「区域和检索 - 数组不可变」的进阶，要求计算子矩阵的元素和。

这道题可以复用「区域和检索 - 数组不可变」的做法，计算矩阵每一行的一维前缀和，计算子矩阵的元素和时遍历子矩阵的每一行，但是该做法的每次查询的时间复杂度和查询范围的行数有关，无法实现 $O(1)$ 时间的查询。使用二维前缀和，则可以实现 $O(1)$ 时间的查询。

解法

思路和算法

为了实现 $O(1)$ 时间的查询，需要预计算整个矩阵的前缀和矩阵。

创建 $(m+1)\times (n+1)$ 的前缀和矩阵 $\text{prefixSums}$，对于 $0\le i\le m$ 和 $0\le j\le n$，$\text{prefixSums}[i][j]$ 表示 $\text{matrix}[i]$ 的行数为 $i$、列数为 $j$ 的前缀和，即行下标范围 $[0,i-1]$、列下标范围 $[0,j-1]$ 中的所有元素之和：

$$\text{prefixSums}[i][j]=\sum _{0\le p<i,0\le q<j}\text{matrix}[p][q]$$

特别地，当 $i$ 和 $j$ 中至少有一个值等于 $0$ 时，$\text{prefixSums}[i][j]=0$。

对于 $0\le i<m$ 和 $0\le j<n$，$\text{prefixSums}[i+1][j+1]$ 的值计算如下：

$$\begin{array}{rl}& \text{prefixSums}[i+1][j+1]\\ =& \text{prefixSums}[i][j+1]\\ & +\text{prefixSums}[i+1][j]\\ & -\text{prefixSums}[i][j]\\ & +\text{matrix}[i][j]\end{array}$$

可以结合下图理解前缀和矩阵的计算方式。

图中的四个区域对应的原始矩阵的行下标范围和列下标范围如下。

• A 区域的行下标范围是 $[0,i-1]$，列下标范围是 $[0,j-1]$。

• B 区域的行下标范围是 $[0,i-1]$，列下标是 $j$。

• C 区域的行下标是 $i$，列下标范围是 $[0,j-1]$。

• D 区域的行下标是 $i$，列下标是 $j$。

前缀和 $\text{prefixSums}[i+1][j+1]$ 应将 A、B、C、D 四个区域各计算一次。计算前缀和的各项中，$\text{prefixSums}[i][j+1]$ 为 A 区域和 B 区域，$\text{prefixSums}[i+1][j]$ 为 A 区域和 C 区域，$\text{prefixSums}[i][j]$ 为 A 区域，$\text{matrix}[i][j]$ 为 D 区域，因此可以通过上述方法计算前缀和矩阵。

得到前缀和矩阵 $\text{prefixSums}$ 之后，对于 $0\le {\text{row}}_1\le {\text{row}}_2<m$ 和 $0\le {\text{col}}_1\le {\text{col}}_2<n$，以 $({\text{row}}_1,{\text{col}}_1)$ 为左上角、$({\text{row}}_2,{\text{col}}_2)$ 为右下角的子矩阵的元素和可以通过前缀和矩阵得到：

$$\begin{array}{rl}& \text{sumRegion}({\text{row}}_1,{\text{col}}_1,{\text{row}}_2,{\text{col}}_2)\\ =& \text{prefixSums}[{\text{row}}_2+1][{\text{col}}_2+1]\\ & -\text{prefixSums}[{\text{row}}_1][{\text{col}}_2+1]\\ & -\text{prefixSums}[{\text{row}}_2+1][{\text{col}}_1]\\ & +\text{prefixSums}[{\text{row}}_1][{\text{col}}_1]\end{array}$$

可以结合下图理解子矩阵元素和的计算方式。

图中的四个区域对应的原始矩阵的行下标范围和列下标范围如下。

• A 区域的行下标范围是 $[0,{\text{row}}_1-1]$，列下标范围是 $[0,{\text{col}}_1-1]$。

• B 区域的行下标范围是 $[0,{\text{row}}_1-1]$，列下标范围是 $[{\text{col}}_1,{\text{col}}_2]$。

• C 区域的行下标范围是 $[{\text{row}}_1,{\text{row}}_2]$，列下标范围是 $[0,{\text{col}}_1-1]$。

• D 区域的行下标范围是 $[{\text{row}}_1,{\text{row}}_2]$，列下标范围是 $[{\text{col}}_1,{\text{col}}_2]$。

需要计算元素和的子矩阵是 D 区域。计算子矩阵元素和的各项中，$\text{prefixSums}[{\text{row}}_2+1][{\text{col}}_2+1]$ 为 A、B、C、D 四个区域，$\text{prefixSums}[{\text{row}}_1][{\text{col}}_2+1]$ 为 A 区域和 B 区域，$\text{prefixSums}[{\text{row}}_2+1][{\text{col}}_1]$ 为 A 区域和 C 区域，$\text{prefixSums}[{\text{row}}_1][{\text{col}}_1]$ 为 A 区域，因此可以通过上述方法计算子矩阵元素和。

代码

class NumMatrix {int[][] prefixSums;public NumMatrix(int[][] matrix) {int m = matrix.length, n = matrix[0].length;prefixSums = new int[m + 1][n + 1];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {prefixSums[i + 1][j + 1] = prefixSums[i][j + 1] + prefixSums[i + 1][j] - prefixSums[i][j] + matrix[i][j];}}}public int sumRegion(int row1, int col1, int row2, int col2) {return prefixSums[row2 + 1][col2 + 1] - prefixSums[row1][col2 + 1] - prefixSums[row2 + 1][col1] + prefixSums[row1][col1];}
}

复杂度分析

• 时间复杂度：构造方法的时间复杂度是 $O(m\times n)$，$\text{sumRegion}$ 操作的时间复杂度是 $O(1)$，其中 $m$ 和 $n$ 分别是矩阵 $\text{matrix}$ 的行数和列数。构造方法需要创建 $(m+1)\times (n+1)$ 的前缀和矩阵并计算每个元素的前缀和，每次 $\text{sumRegion}$ 操作计算子矩阵的元素和的时间是 $O(1)$。

• 空间复杂度：$O(m\times n)$，其中 $m$ 和 $n$ 分别是矩阵 $\text{matrix}$ 的行数和列数。需要创建 $(m+1)\times (n+1)$ 的前缀和矩阵。