304. Range Sum Query 2D - Immutable

T: sumRegion: O(1)

S: O(mn)

class NumMatrix {

    int[][] presum;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        if (m == 0 && n == 0) {
            return;
        }
        
        presum = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // matrix[i- 1][j - 1] =  preSum[i][j] - preSum[i-1][j] - preSum[i][j-1] + preSum[i-1][j-1]
                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[row1][col2+1] - presum[row2+1][col1] + presum[row1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 
 2 1 4 3 red
 1 2 2 4 bule
 1 1 2 2 green
 
 presum [0, 0, 4, 4]
 
 preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i
- 1][j - 1] - preSum[i-1][j-1];


matrix[i- 1][j - 1] =  preSum[i][j] - preSum[i-1][j] - preSum[i][j-1] + preSum[i-1][j-1]
 
 */