303. Range Sum Query - Immutable

class NumArray:
 # time O(N) space O(1)
    def __init__(self, nums: List[int]):
        n = len(nums)
        self.psum = [0] * (n+1)
        for i in range(n):
            self.psum[i+1] = self.psum[i] + nums[i]# psun[i]: sum of num[0]++num[i]

    def sumRange(self, i: int, j: int) -> int:
        return self.psum[j+1] - self.psum[i]
#################################################################################
class NumArray:
    """
    main idea: prefix sum
    """

    def __init__(self, A: List[int]):
        """tc O(N) sc O(N)   => can optimized to sc O(1)
        """
        n = len(A)
        self.psum = [None] * n
        self.psum[0] = A[0]
        for i in range(1,n):
            self.psum[i] = self.psum[i-1] + A[i]

    def sumRange(self, left: int, right: int) -> int:
        """ tc O(1) sc O(1)
        """
        if left == 0:
            return self.psum[right]
        return self.psum[right] - self.psum[left-1]