Question

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example:
Given 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

Code

public class NumMatrix {
    private int[][] sum;//sum[i][j]表示matrix中以(0,0)为左上，(i - 1, j - 1)为右下的矩阵中所有元素之和

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return;
        int m = matrix.length, n = matrix[0].length;
        sum = new int[m + 1][n + 1];//第一行第一列为全0，以免越界检查
        
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];//sum[i][j]等于matrix[i - 1][j - 1] + 以(i - 1, j)为右下的矩阵之和 + 该行从[i, 0] ~ [i, j - 1]之和。以(i, j - 1)为右下的矩阵之和 - 以(i - 1, j - 1)为右下的矩阵之和即为该行从[i, 0] ~ [i, j - 1]之和。
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (sum == null) return 0;
        return sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1];
    }
}


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

Solution

sum[i][j]表示matrix中以(0,0)为左上，(i - 1, j - 1)为右下的矩阵中所有元素之和。

sum[i][j]等于matrix[i - 1][j - 1] + 以(i - 1, j)为右下的矩阵之和 + 该行从[i, 0] ~ [i, j - 1]之和。以(i, j - 1)为右下的矩阵之和 - 以(i - 1, j - 1)为右下的矩阵之和即为该行从[i, 0] ~ [i, j - 1]之和。

所求的区域之和 = sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1]。