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]