303. Range Sum Query - Immutable

Approach 1: Pre-sum/ Cumulative PreSum

class NumArray(object):
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        su = 0
        self.l = [0]
        for i in nums:
            su += i
            self.l.append(su) 
            
    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.l[j+1]-self.l[i]

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

When we initialize the NumArray we can keep track of the sums of each of the positions, and eventually when sumRange is called we can just subtract the sums between position j and position i

Time Complexity: O(N) [init method] O(1) [sumRange]

Space Complexity: O(N)