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

题目描述

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

示例：

给定 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
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

提示：

你可以假设矩阵不可变。
会多次调用 sumRegion 方法。
你可以假设 row1 ≤ row2 且 col1 ≤ col2 。

题解

法一：一维前缀和

对每一行分别做一维数组的前缀和，检索时对二维区域中的每一行计算子数组和，然后对每一行的子数组和计算总和。

具体实现如下（一个小trick：将列数设为n+1并将首位设为0，可以避免对col=0时的讨论

class NumMatrix {
    int[][] sums;

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

复杂度分析

时间复杂度：初始化 $O(mn)$，每次检索 $O(m)$，其中 m 和 n 分别是矩阵 $\textit{matrix}$ 的行数和列数。
初始化需要遍历矩阵 matrix 计算二维前缀和，时间复杂度是 $O(mn)$。
每次检索需要对二维区域中的每一行计算子数组和，二维区域的行数不超过 m，计算每一行的子数组和的时间复杂度是 $O(1)$，因此每次检索的时间复杂度是 $O(m)$。

空间复杂度：$O(mn)$，其中 m 和 n 分别是矩阵 matrix 的行数和列数。需要创建一个 m 行n+1 列的前缀和数组 sums。

法二：二维前缀和

方法一虽然利用了前缀和，但是每次检索的时间复杂度是 $O(m)$，仍然没有降到 $O(1)$。为了将每次检索的时间复杂度降到 $O(1)$，需要使用二维前缀和，在初始化的时候计算二维前缀和数组。

假设 m 和 n 分别是矩阵 matrix 的行数和列数。定义当 $0 \le i<m$ 且 $0 \le j<n$ 时，f(i,j) 为矩阵 matrix 的以 (i,j) 为右下角的子矩阵的元素之和，则：
$$
f(i,j)=f(i−1,j)+f(i,j−1)−f(i−1,j−1)+matrix[i][j]
$$
因此在初始化的时候，即可对所有$ 0 \le i<m$ 和 $0 \le j<n$计算得到 f(i,j) 的值。

同理，我们将第一行和第一列设置为0，避免对边界进行讨论，那么在检索时，就有：
$$
sumRegion(row 1,col 1,row 2,col 2)
=sums[row 2+1][col 2+1]−sums[row 1][col 2+1]−sums[row 2+1][col 1]+sums[row 1][col 1]
$$
具体代码如下：

public class NumMatrix {
    private int[][] sumMatrix;

    public NumMatrix(int[][] matrix) {
        int row = matrix.length;
        if(row > 0){
            int col = matrix[0].length;
            sumMatrix = new int[row + 1][col + 1];

            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    sumMatrix[i + 1][j + 1] = sumMatrix[i][j + 1] + sumMatrix[i + 1][j] - sumMatrix[i][j] + matrix[i][j];
                }
            }
        }
    }

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

复杂度分析

时间复杂度：初始化 $O(mn)$，每次检索 $O(1)$，其中 m 和 n 分别是矩阵 matrix 的行数和列数。
初始化需要遍历矩阵 matrix 计算二维前缀和，时间复杂度是 $O(mn)$。
每次检索的时间复杂度是 $O(1)$。

空间复杂度：$O(mn)$，其中 m 和 n 分别是矩阵 matrix 的行数和列数。需要创建一个 m+1 行 n+1 列的二维前缀和数组 sums。

参考

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/er-wei-qu-yu-he-jian-suo-ju-zhen-bu-ke-b-2z5n/