题目描述
给定一个二维矩阵 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：
提示：
- 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 方法
题目解析
标这题的思路和 303. 区域和检索 – 数组不可变 中一维数组中的前缀和问题是非常类似的，如下图：
如果我想计算红色的这个子矩阵的元素之和，可以用绿色矩阵减去蓝色矩阵减去橙色矩阵最后加上粉色矩阵，而绿蓝橙粉这四个矩阵有一个共同的特点，就是左上角就是 (0, 0) 原点。
那么我们可以维护一个二维 preSum 数组，专门记录以原点为顶点的矩阵的元素之和，就可以用几次加减运算算出任何一个子矩阵的元素和。
参考代码
以下为 Java 代码。
复杂度分析
- 时间复杂度：初始化 O(mn)，每次检索 O(1)，其中 m 和 n 分别是矩阵 matrix 的行数和列数。
- 初始化需要遍历矩阵 matrix 计算二维前缀和，时间复杂度是 O(mn)。
- 每次检索的时间复杂度是 O(1)。
- 空间复杂度：O(mn)，其中 m 和 n 分别是矩阵 matrix 的行数和列数。需要创建一个 m+1 行 n+1 列的二维前缀和数组 sums。
