302. 2D prefix sum

class NumMatrix:

    def __init__(self, m: List[List[int]]):
        r,c=len(m),len(m[0])
        self.dp=dp=[[0]*(c+1) for i in range(r+1)]
        #final sum from (0,0) to (r,c) of matrix m stores at (r+1,c+1)

        #we will go with 0-index array only but update on dp
        for i in range(r):
            prefix=0 #current row prefix sum=0
            for j in range(c):
                prefix+=m[i][j]  #add next element in the row
                above=dp[i][j+1] #add above (i+1,j+1) of dp table
                dp[i+1][j+1]=prefix+above
                #store at i+1 j+1


    def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
        #sum1=dp[r1+1][c1+1]
        #we will increment by 1 beacuase we are storing sums in 1 indexed array
        r1,r2,c1,c2=r1+1,r2+1,c1+1,c2+1
        dp=self.dp
        corner=dp[r1-1][c1-1]
        left=dp[r2][c1-1]
        top=dp[r1-1][c2]
        total=dp[r2][c2]
        return total-left-top+corner
    #we are substracting it because it is common part of left and top

# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)