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

给定一个二维矩阵 matrix，以下类型的多个请求：

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

实现 NumMatrix 类：

• NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
• int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

示例 1：

**输入:** 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[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]]
**输出:** 
[null, 8, 11, 12]

**解释:**
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]]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -105 <= matrix[i][j] <= 105
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• 最多调用 104 次 sumRegion 方法

注意：本题与主站 304 题相同： <https://leetcode-cn.com/problems/range-sum-
query-2d-immutable/>

方法一：一维前缀和

初始化时对矩阵的每一行计算前缀和，检索时对二维区域中的每一行计算子数组和，然后对每一行的子数组和计算总和。

具体实现方面，创建 m 行 n+1 列的二维数组 sums，其中 m 和 n 分别是矩阵 matrix 的行数和列数，sums}[i] 为 matrix}[i] 的前缀和数组。将 sums 的列数设为 n+1 的目的是为了方便计算每一行的子数组和，不需要对 col}_1=0 的情况特殊处理。

[sol1-Java]

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;
    }
}

[sol1-JavaScript]

var NumMatrix = function(matrix) {
    const m = matrix.length;
    if (m > 0) {
        const n = matrix[0].length;
        this.sums = new Array(m).fill(0).map(() => new Array(n + 1).fill(0));
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                this.sums[i][j + 1] = this.sums[i][j] + matrix[i][j];
            }
        }
    }
};

NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    let sum = 0;
    for (let i = row1; i <= row2; i++) {
        sum += this.sums[i][col2 + 1] - this.sums[i][col1];
    }
    return sum;
};

[sol1-Golang]

type NumMatrix struct {
    sums [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    sums := make([][]int, len(matrix))
    for i, row := range matrix {
        sums[i] = make([]int, len(row)+1)
        for j, v := range row {
            sums[i][j+1] = sums[i][j] + v
        }
    }
    return NumMatrix{sums}
}

func (nm *NumMatrix) SumRegion(row1, col1, row2, col2 int) (sum int) {
    for i := row1; i <= row2; i++ {
        sum += nm.sums[i][col2+1] - nm.sums[i][col1]
    }
    return
}

[sol1-Python3]

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), (len(matrix[0]) if matrix else 0)
        self.sums = [[0] * (n + 1) for _ in range(m)]
        _sums = self.sums

        for i in range(m):
            for j in range(n):
                _sums[i][j + 1] = _sums[i][j] + matrix[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        _sums = self.sums

        total = sum(_sums[i][col2 + 1] - _sums[i][col1] for i in range(row1, row2 + 1))
        return total

[sol1-C++]

class NumMatrix {
public:
    vector<vector<int>> sums;

    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m > 0) {
            int n = matrix[0].size();
            sums.resize(m, vector<int>(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];
                }
            }
        }
    }

    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;
    }
};

[sol1-C]

typedef struct {
    int** sums;
    int sumsSize;
} NumMatrix;

NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) {
    NumMatrix* ret = malloc(sizeof(NumMatrix));
    ret->sums = malloc(sizeof(int*) * matrixSize);
    ret->sumsSize = matrixSize;
    for (int i = 0; i < matrixSize; i++) {
        ret->sums[i] = malloc(sizeof(int) * (matrixColSize[i] + 1));
        ret->sums[i][0] = 0;
        for (int j = 0; j < matrixColSize[i]; j++) {
            ret->sums[i][j + 1] = ret->sums[i][j] + matrix[i][j];
        }
    }
    return ret;
}

int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) {
    int sum = 0;
    for (int i = row1; i <= row2; i++) {
        sum += obj->sums[i][col2 + 1] - obj->sums[i][col1];
    }
    return sum;
}

void numMatrixFree(NumMatrix* obj) {
    for (int i = 0; i < obj->sumsSize; i++) {
        free(obj->sums[i]);
    }
    free(obj->sums);
}

复杂度分析

• 时间复杂度：初始化 O(mn)，每次检索 O(m)，其中 m 和 n 分别是矩阵 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)=\sum\limits_{p=0}^i \sum\limits_{q=0}^j \textit{matrix}[p][q]

当 i=0 或 j=0 时，计算 f(i,j) 只需要对矩阵 matrix 的最上边的行和最左边的列分别计算前缀和即可。当 i 和 j 都大于 0 时，如何计算 f(i,j) 的值？

当 i 和 j 都大于 0 时，假设计算 f(i,j) 时已经知道了 f(i-1,j)、f(i,j-1) 和 f(i-1,j-1) 的值。为了计算 f(i,j)，自然而然会想到使用 f(i-1,j)、f(i,j-1) 和 matrix}[i][j] 的值。

注意到 f(i-1,j) 和 f(i,j-1) 这两项涉及到的矩阵 matrix 的元素有重合，矩阵 matrix 的以 (i-1,j-1) 为右下角的子矩阵都在这两项中出现。因此如果计算 f(i-1,j)+f(i,j-1)+\textit{matrix}[i][j]，则该结果值比 f(i,j) 多了 f(i-1,j-1)，因此 f(i,j) 的计算如下：

f(i,j)=f(i-1,j)+f(i,j-1)-f(i-1,j-1)+\textit{matrix}[i][j]

具体推导如下：

\begin{aligned}
&\quad \ f(i,j) \
&=\sum\limits_{p=0}^{i-1} \sum\limits_{q=0}^{j-1} \textit{matrix}[p][q]+\sum\limits_{p=0}^{i-1} \textit{matrix}[p][j]+\sum\limits_{q=0}^{j-1} \textit{matrix}[i][q]+\textit{matrix}[i][j] \
&=\Big(\sum\limits_{p=0}^{i-1} \sum\limits_{q=0}^{j-1} \textit{matrix}[p][q]+\sum\limits_{p=0}^{i-1} \textit{matrix}[p][j]\Big) \
&\quad+\Big(\sum\limits_{p=0}^{i-1} \sum\limits_{q=0}^{j-1} \textit{matrix}[p][q]+\sum\limits_{q=0}^{j-1} \textit{matrix}[i][q]\Big) \
&\quad-\sum\limits_{p=0}^{i-1} \sum\limits_{q=0}^{j-1} \textit{matrix}[p][q] \
&\quad+\textit{matrix}[i][j] \
&=\sum\limits_{p=0}^{i-1} \sum\limits_{q=0}^j \textit{matrix}[p][q]+\sum\limits_{p=0}^i \sum\limits_{q=0}^{j-1} \textit{matrix}[p][q]-\sum\limits_{p=0}^{i-1} \sum\limits_{q=0}^{j-1} \textit{matrix}[p][q]+\textit{matrix}[i][j] \
&=f(i-1,j)+f(i,j-1)-f(i-1,j-1)+\textit{matrix}[i][j]
\end{aligned}

因此在初始化的时候，即可对所有 0 \le i<m 和 0 \le j<n 计算得到 f(i,j) 的值。

检索时，应利用预处理得到的 f 的值。当 row}_1=0 且 col}_1=0 时，sumRegion}(\textit{row}_1,\textit{col}_1,\textit{row}_2,\textit{col}_2)=f(\textit{row}_2,\textit{col}_2)。

当 row}_1 \le \textit{row}_2 且 col}_1 \le \textit{col}_2 时，sumRegion}(\textit{row}_1,\textit{col}_1,\textit{row}_2,\textit{col}_2) 可以写成如下形式：

\begin{aligned}
&\quad \ \text{sumRegion}(\textit{row}_1,\textit{col}_1,\textit{row}_2,\textit{col}_2) \
&=\text{sumRegion}(0,0,\textit{row}_2,\textit{col}_2) \
&\quad-\text{sumRegion}(0,\textit{col}_1,\textit{row}_1-1,\textit{col}_2) \
&\quad-\text{sumRegion}(\textit{row}_1,0,\textit{row}_2,\textit{col}_1-1) \
&\quad-\text{sumRegion}(0,0,\textit{row}_1-1,\textit{col}_1-1) \
&=\text{sumRegion}(0,0,\textit{row}_2,\textit{col}_2) \
&\quad-(\text{sumRegion}(0,\textit{col}_1,\textit{row}_1-1,\textit{col}_2)+\text{sumRegion}(0,0,\textit{row}_1-1,\textit{col}_1-1)) \
&\quad-(\text{sumRegion}(\textit{row}_1,0,\textit{row}_2,\textit{col}_1-1)+\text{sumRegion}(0,0,\textit{row}_1-1,\textit{col}_1-1)) \
&\quad-\text{sumRegion}(0,0,\textit{row}_1-1,\textit{col}_1-1) \
&\quad+2 \times \text{sumRegion}(\textit{row}_1,0,\textit{row}_2,\textit{col}_1-1) \
&=\text{sumRegion}(0,0,\textit{row}_2,\textit{col}_2) \
&\quad-\text{sumRegion}(0,0,\textit{row}_1-1,\textit{col}_2) \
&\quad-\text{sumRegion}(0,0,\textit{row}_2,\textit{col}_1-1) \
&\quad+\text{sumRegion}(0,0,\textit{row}_1-1,\textit{col}_1-1) \
&=f(\textit{row}_2,\textit{col}_2)-f(\textit{row}_1-1,\textit{col}_2)-f(\textit{row}_2,\textit{col}_1-1)+f(\textit{row}_1-1,\textit{col}_1-1)
\end{aligned}

<,,,>

即可在 O(1) 时间内得到 sumRegion}(\textit{row}_1,\textit{col}_1,\textit{row}_2,\textit{col}_2) 的值。

具体实现方面，创建 m+1 行 n+1 列的二维数组 sums，其中 sums}[i+1][j+1] 的值为上述 f(i,j) 的值。

将 sums 的行数和列数分别设为 m+1 和 n+1 的目的是为了方便计算 sumRegion}(\textit{row}_1,\textit{col}_1,\textit{row}_2,\textit{col}_2) ，不需要对 row}_1=0 和 col}_1=0 的情况特殊处理。此时有：

\begin{aligned}
&\quad \ \text{sumRegion}(\textit{row}_1,\textit{col}_1,\textit{row}_2,\textit{col}_2) \
&=\textit{sums}[\textit{row}_2+1][\textit{col}_2+1]-\textit{sums}[\textit{row}_1][\textit{col}_2+1]-\textit{sums}[\textit{row}_2+1][\textit{col}_1]+\textit{sums}[\textit{row}_1][\textit{col}_1]
\end{aligned}

[sol2-Java]

class NumMatrix {
    int[][] sums;

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

[sol2-JavaScript]

var NumMatrix = function(matrix) {
    const m = matrix.length;
    if (m > 0) {
        const n = matrix[0].length;
        this.sums = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                this.sums[i + 1][j + 1] = this.sums[i][j + 1] + this.sums[i + 1][j] - this.sums[i][j] + matrix[i][j];
            }
        }
    }
};

NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    return this.sums[row2 + 1][col2 + 1] - this.sums[row1][col2 + 1] - this.sums[row2 + 1][col1] + this.sums[row1][col1];
};

[sol2-Golang]

type NumMatrix struct {
    sums [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    m := len(matrix)
    if m == 0 {
        return NumMatrix{}
    }
    n := len(matrix[0])
    sums := make([][]int, m+1)
    sums[0] = make([]int, n+1)
    for i, row := range matrix {
        sums[i+1] = make([]int, n+1)
        for j, v := range row {
            sums[i+1][j+1] = sums[i+1][j] + sums[i][j+1] - sums[i][j] + v
        }
    }
    return NumMatrix{sums}
}

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

[sol2-Python3]

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), (len(matrix[0]) if matrix else 0)
        self.sums = [[0] * (n + 1) for _ in range(m + 1)]
        _sums = self.sums

        for i in range(m):
            for j in range(n):
                _sums[i + 1][j + 1] = _sums[i][j + 1] + _sums[i + 1][j] - _sums[i][j] + matrix[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        _sums = self.sums

        return _sums[row2 + 1][col2 + 1] - _sums[row1][col2 + 1] - _sums[row2 + 1][col1] + _sums[row1][col1]

[sol2-C++]

class NumMatrix {
public:
    vector<vector<int>> sums;

    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m > 0) {
            int n = matrix[0].size();
            sums.resize(m + 1, vector<int>(n + 1));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }

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

[sol2-C]

typedef struct {
    int** sums;
    int sumsSize;
} NumMatrix;

NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) {
    NumMatrix* ret = malloc(sizeof(NumMatrix));
    ret->sums = malloc(sizeof(int*) * (matrixSize + 1));
    ret->sumsSize = matrixSize + 1;
    int n = matrixSize ? matrixColSize[0] : 0;
    for (int i = 0; i <= matrixSize; i++) {
        ret->sums[i] = malloc(sizeof(int) * (n + 1));
        memset(ret->sums[i], 0, sizeof(int) * (n + 1));
    }
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < matrixColSize[i]; j++) {
            ret->sums[i + 1][j + 1] = ret->sums[i][j + 1] + ret->sums[i + 1][j] - ret->sums[i][j] + matrix[i][j];
        }
    }
    return ret;
}

int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) {
    return obj->sums[row2 + 1][col2 + 1] - obj->sums[row1][col2 + 1] - obj->sums[row2 + 1][col1] + obj->sums[row1][col1];
}

void numMatrixFree(NumMatrix* obj) {
    for (int i = 0; i < obj->sumsSize; i++) {
        free(obj->sums[i]);
    }
    free(obj->sums);
}

复杂度分析

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

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