Range Sum Query 2D
Given a 2D matrix `matrix`, find the sum of the elements inside the rectangle defined by its upper left corner `(row1, col1)` and lower right corner `(row2, col2)`.
Constraints:
- 1 <= matrix.length <= 200
- 1 <= matrix[0].length <= 200
- 0 <= row1 <= row2 < matrix.length
- 0 <= col1 <= col2 < matrix[0].length
Examples:
Input: [[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]]
Output: 8
Explanation: Sum of elements in the rectangle from (2, 1) to (4, 3) is 8 (i.e., 1 + 7 + 0).
Solutions
Prefix Sum
We use a prefix sum array `dp` where `dp[i][j]` is the sum of all elements in the rectangle from `(0, 0)` to `(i - 1, j - 1)`. We can then calculate the sum of the elements in the rectangle from `(row1, col1)` to `(row2, col2)` as `dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1]`.
class NumMatrix:
def __init__(self, matrix):
self.dp = [[0] * (len(matrix[0]) + 1) for _ in range(len(matrix) + 1)] for i in range(1, len(matrix) + 1):
for j in range(1, len(matrix[0]) + 1):
self.dp[i][j] = self.dp[i - 1][j] + self.dp[i][j - 1] - self.dp[i - 1][j - 1] + matrix[i - 1][j - 1]
def sumRegion(self, row1, col1, row2, col2):
return self.dp[row2 + 1][col2 + 1] - self.dp[row2 + 1][col1] - self.dp[row1][col2 + 1] + self.dp[row1][col1]Follow-up:
What if the matrix is very large and we need to query the sum of the elements in the rectangle many times?
