Range Sum Query - Immutable

Intuition

Answering a range sum by adding up elements takes time proportional to the range length, which is wasteful when many queries hit the same immutable array. Instead, precompute prefix[i] = nums[0] + nums[1] + ... + nums[i - 1], where prefix[0] = 0. Then the sum of nums[left..right] equals prefix[right + 1] - prefix[left], because the shared prefix up to left cancels out. The one extra leading zero in the prefix array removes any special-casing when left is 0. Building the prefix array is a single linear pass, and afterward each query is a single subtraction.

Algorithm walkthrough

1. 1In the constructor, allocate a prefix array of length n + 1 and set prefix[0] = 0.
2. 2For each index i from 0 to n - 1, set prefix[i + 1] = prefix[i] + nums[i], accumulating the running total.
3. 3Store the prefix array on the instance so it can be reused across queries.
4. 4For sumRange(left, right), return prefix[right + 1] - prefix[left].
5. 5The subtraction cancels the common prefix up to index left, leaving exactly the sum of nums[left..right].

Implementation

class NumArray:
    def __init__(self, nums: list[int]):
        self.prefix = [0] * (len(nums) + 1)
        for i, num in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + num

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]