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

二、解题思路

这个问题可以通过使用一个辅助的前缀和矩阵来解决。前缀和矩阵是一个二维数组，其中每个元素 dp[i][j] 表示从原点 (0, 0) 到 (i-1, j-1) 形成的矩形区域的所有元素之和。

初始化时，我们遍历整个输入矩阵，并计算每个位置的前缀和。计算前缀和时，可以使用以下关系：

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]

这里的 dp[i-1][j] 是当前位置上方元素的前缀和，dp[i][j-1] 是当前位置左侧元素的前缀和，而 dp[i-1][j-1] 是左上角元素的前缀和，我们加了一次，所以要减去。最后加上当前位置的元素值 matrix[i-1][j-1]。

当我们需要计算 (row1, col1) 到 (row2, col2) 的子矩阵和时，我们可以利用前缀和矩阵快速计算：

sumRegion(row1, col1, row2, col2) = dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1] + dp[row1][col1]

这里的 dp[row2+1][col2+1] 是 (row2, col2) 的前缀和，而其他三项分别减去的是超出 (row1, col1) 到 (row2, col2) 范围的部分。

三、具体代码

class NumMatrix {
    private int[][] dp;

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

在这个实现中，我们初始化了一个大小为 (m+1) x (n+1) 的前缀和矩阵 dp，以处理边界情况，这样我们就不需要在计算时对边界进行特殊处理。每次调用 sumRegion 方法时，我们只需要常数时间复杂度即可得到子矩阵的和。

四、时间复杂度和空间复杂度

1. 时间复杂度