Range Sum Query - Immutable

Problem Summary

• Given an array [-2, 0, 3, -5, 2, -1], you need to implement two functions:
  • __init__()
  • sumRange(left, right): int
• sumRange will be given two indices, starting (inclusive) and ending (inclusive), you need to return the sum of the range

Why This Works

• We calculate the prefix sum of all elements and then query is just $O(1)$ lookups

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Prefix Sum

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterate through it just once. Subsequent queries are $O(1)$
• Space: $O(n)$ → Reason: Storing a calculated prefix sum array

Code

class NumArray:
    def __init__(self, nums: List[int]):
        total = 0
        self.prefix = []
        for num in nums:
            total += num
            self.prefix.append(total)

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

Common Mistakes / Things I Got Stuck On

• Over complicated the implementation by also calculating suffix sum
• Should have walk through the whole plan before diving into implementation