[link](https://leetcode.com/problems/range-sum-query-2d-immutable/)

---

Given a 2D matrix matrix, handle multiple queries of the following type:

- Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Implement the NumMatrix class:

- NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
- int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

You must design an algorithm where sumRegion works on O(1) time complexity.

#### Example 1:


Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]

Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

#### Constraints:

- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- -104 <= matrix[i][j] <= 104
- 0 <= row1 <= row2 < m
- 0 <= col1 <= col2 < n
- At most 104 calls will be made to sumRegion.

---

The __init__ method initializes the NumMatrix object with a 2D matrix of integers matrix. It calculates and stores the prefix sum of the input matrix row by row in the prefixGrid list.

The sumRegion method takes four parameters row1, col1, row2, and col2, and returns the sum of the elements in the submatrix defined by the top-left corner (row1, col1) and the bottom-right corner (row2, col2) (both inclusive). It does this efficiently using prefix sums by calculating the sum of each row within the given column range.

#### Solution 1:

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.prefixGrid = []
        for i in range(len(matrix)):
            row = []
            total = 0
            for j in range(len(matrix[i])):
                total += matrix[i][j]
                row.append(total)
            self.prefixGrid.append(row)       

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        res = 0
        for i in range(row1, row2 + 1):
            if col1 > 0:
                res += (self.prefixGrid[i][col2] - self.prefixGrid[i][col1 - 1])
            else:
                res += (self.prefixGrid[i][col2] - 0)
        return res    
        

O(T): O(m * n)
O(S): O(m * n)

---

We can create a new 2D list called prefixGrid with dimensions (ROWS + 1) x (COLS + 1). The extra row and column are added to simplify the implementation of prefix sums.

The purpose of this prefixGrid is to store the 2D prefix sums of the input matrix. Each element prefixGrid[i][j] represents the sum of all elements in the submatrix that starts from the top-left corner (0, 0) and ends at the cell (i-1, j-1) of the input matrix. In other words, it calculates the prefix sum for each row and column in the input matrix.

The prefix sum calculation in the nested loop:

- It uses two nested loops to traverse the input matrix.
- The outer loop iterates over the rows of the matrix.
- The inner loop iterates over the columns of the matrix.
- For each element at position (r, c) in the input matrix, it calculates the prefix sum by adding the current element's value to the value of the above element (prefix sum from the previous row) and the value of the left element (prefix sum from the previous column).
- The result is stored in the corresponding position (r+1, c+1) in the prefixGrid.

Sum Region Query (sumRegion method):

The sumRegion method takes four parameters row1, col1, row2, and col2, which define the top-left corner (row1, col1) and the bottom-right corner (row2, col2) of the submatrix for which we want to calculate the sum.
- The method then adjusts the parameters to work with the prefixGrid. Specifically, it increments all parameters by 1, as prefixGrid has an additional row and column.

Using these prefix sum values, it calculates the sum of the elements in the submatrix as follows:

sum(submatrix) = bottomRight - above - left + topLeft.

The final result is returned as the sum of the submatrix.

#### Solution 2

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        ROWS, COLS = len(matrix), len(matrix[0])
        self.prefixGrid = [[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.prefixGrid[r][c + 1]
                self.prefixGrid[r + 1][c + 1] = prefix + above


    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        row1, row2, col1, col2 = row1 + 1, row2 + 1, col1 + 1, col2 + 1
        bottomRight = self.prefixGrid[row2][col2]
        above = self.prefixGrid[row1 - 1][col2]
        left = self.prefixGrid[row2][col1 - 1]
        topLeft = self.prefixGrid[row1 - 1][col1 - 1]
        return (bottomRight - above - left + topLeft)
        

O(T): O(m * n), O(1)
O(S): O(m * n)