剑指 Offer II 013. 二维子矩阵的和(Java)

class NumMatrix {
    int[][] sum = null;
    public NumMatrix(int[][] matrix) {
        sum = new int[matrix.length+1][matrix[0].length+1];
        for (int i = 0; i < matrix.length; i++) {
            int s = 0;
            for (int j = 0; j < matrix[i].length; j++) {
                s += matrix[i][j];
                sum[i+1][j+1] = sum[i][j+1]+s;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2+1][col2+1]-sum[row2+1][col1]-sum[row1][col2+1]+sum[row1][col1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17