304. Range Sum Query 2D - Immutable

题目 304. Range Sum Query 2D - Immutable

思路分析

偏移1位

代码实现

class NumMatrix {

    int[][] preSum;

    public NumMatrix(int[][] matrix) {
        int n = matrix.length;
        if (n == 0) return;
        int m = matrix[0].length;
     
        preSum = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2 + 1][col2 + 1] 
             - preSum[row2 + 1][col1] 
             - preSum[row1][col2 + 1] 
             + preSum[row1][col1];
    }
}

同类题型

视频讲解