Range Sum Query 2D - Immutable

Range Sum Query 2D - Immutable

前缀和数组在 2D 上的应用，注意处理好 padding 和 index offset 就行了。

public class NumMatrix {
    int[][] dp;
    public NumMatrix(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return;

        int rows = matrix.length;
        int cols = matrix[0].length;

        dp = new int[rows + 1][cols + 1];

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + matrix[i][j];
            }
        }
    }

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