Range Sum Query 2D - Immutable

https://leetcode.com/problems/range-sum-query-2d-immutable/

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        ROWS, COLS = len(matrix) , len(matrix[0])
        self.sumMat = [[0] * (COLS + 1) for c in range(ROWS+1)]

        for r in range(ROWS):
            prefix = 0
            for c in range(COLS):
                prefix += matrix[r][c]
                above = self.sumMat[r][c+1]
                self.sumMat[r + 1][c + 1] = prefix + above
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int):
        r1, c1, r2, c2 = row1 + 1, col1 + 1, row2 + 1, col2 +1

        bottomRight = self.sumMat[r2][c2]
        above = self.sumMat[r1-1][c2]
        left = self.sumMat[r2][c1-1]
        topLeft = self.sumMat[r1 -1][c1 -1]

        return bottomRight - above - left + topLeft

just like 1d prefix sum problem , we are gonna extend it to 2d.

1st row is same, from 2nd row we are going to add above prefix sum to current position

so in case of calculating [1,1]  =  prefix sum from [1,0] [1,1]  + above prefix sum which is stored in [0,1] == [0,0] +[0,1]

that is the init part, adding extra 0 padding is to eliminate edge case of for loop overflow

 

and when calculating we are going to removing the surrounding shell of what we actually want to sum.