303. Range Sum Query - Immutable
- 思路
- example
- 前缀和 1D preSum
preSum[right+1] - preSum[left]
- 复杂度. 时间：O(n), 空间: O(n)
class NumArray:
def __init__(self, nums: List[int]):
n = len(nums)
self.preSum = [0 for _ in range(n+1)]
for i in range(1, n+1):
self.preSum[i] += self.preSum[i-1] + nums[i-1]
def sumRange(self, left: int, right: int) -> int:
return self.preSum[right+1] - self.preSum[left]
304. Range Sum Query 2D - Immutable
- 思路
- example
- 前缀和 2D
(row2+1, col2+1) - (row1, col2+1) - (row2+1, col1) + (row1, col1)
- 复杂度. 时间：O(?), 空间: O(?)
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
m, n = len(matrix), len(matrix[0])
self.preSum = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
self.preSum[i][j] = self.preSum[i-1][j] + self.preSum[i][j-1] - self.preSum[i-1][j-1] + matrix[i-1][j-1]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return self.preSum[row2+1][col2+1] - self.preSum[row1][col2+1] - self.preSum[row2+1][col1] + self.preSum[row1][col1]
