303. Range Sum Query - Immutable

https://leetcode.com/problems/range-sum-query-immutable/

Python

Cache the sum of ranges on initial

• INIT
  • Time: O(N)
  • Space: O(N)
• Call sumRange
  • Time: O(1)
  • Space: O(1)

class NumArray:
    def __init__(self, nums: List[int]):
        cache = [0]*len(nums)
        cache[0] = nums[0]

        for i in range(1, len(nums)):
            cache[i] = cache[i-1] + nums[i]

        self.cache = cache


    def sumRange(self, left: int, right: int) -> int:
        if left == 0:
            return self.cache[right]
        else:
            return self.cache[right] - self.cache[left-1]