Range Sum Query Immutable

---

Intuition

• Brute force, simply loop to each element from left to right inclusive and add to the sum.
• To optimize, use a prefix and add from right prefix to left - 1th prefix

Complexity

Runtime

$O(1)$ per call, so $O(N)$ where N is the number of calls

Space

$O(N)$ to precompute the prefix

Code

Prefix

class NumArray:
    def __init__(self, nums: List[int]):
        self.prefix = [nums[0]]
        for i in range(1, len(nums)):
            self.prefix.append(self.prefix[i - 1] + nums[i])
        
    def sumRange(self, left: int, right: int) -> int:
        if left == 0:
            return self.prefix[right]
        return self.prefix[right] - self.prefix[left - 1] 
 
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

Cards

START Basic Front: Range Sum Query Immutable Back: Use a prefix from right prefix - left - 1th prefix END

---

References

• Range Sum Query Immutable