Leetcode 0303. Range Sum Query - Immutable

Problem statement

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

Solution

In this problem we are given tha our nums are immutable, that is we do not need to support operation for changing them. So, what we need to do is to precalculate some information, such that we can quickly compute sums in range. This information is cumulative sums: if we calculate all of them we can compute sum in any range as difference of two cumulative sums.

Complexity

It is just O(n) for time and space for initialization and O(1) time and space for query.

Code

class NumArray:
    def __init__(self, nums):
        self.arr = [0] + list(accumulate(nums))
        
    def sumRange(self, left, right):
        return self.arr[right + 1] - self.arr[left]