Range Sum Query - Immutable (LeetCode 303)

The problem

You are given an integer array nums that never changes. Build a class that answers many queries of the form sumRange(i, j): the sum of nums[i] through nums[j], both ends included.

nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1     (-2 + 0 + 3)
sumRange(2, 5) -> -1    (3 - 5 + 2 - 1)
sumRange(0, 5) -> -3    (the whole array)

How to think about it

Start with brute force. For each query, loop from i to j and add. That is O(n) per query. With up to 10⁴ queries on an array of 10⁴ numbers, you re-add the same elements again and again, around 10⁸ operations.

The key insight: the array is immutable, so precompute once. Build pre[k] = the sum of the first k elements, with pre[0] = 0. Then the sum of nums[i..j] is everything up to j minus everything before i: pre[j+1] - pre[i]. That is a single subtraction, O(1), no matter how long the range is.

Why the extra leading zero? It removes the special case for i = 0. Without it you would need if i == 0: return pre[j]. With it, one formula covers every query.

Which pattern is this? Prefix sums. The tell is “many sum queries over ranges of a fixed array”. Pay a one-time O(n) cost so every query becomes O(1).

Approach

1. In the constructor, start pre = [0].
2. For each x in nums, append pre[-1] + x. Now pre has n + 1 entries and pre[k] is the sum of nums[0..k-1].
3. For sumRange(i, j), return pre[j+1] - pre[i].

Solution

class NumArray:
    def __init__(self, nums):
        self.pre = [0]                         # pre[0] = 0: empty prefix
        for x in nums:
            self.pre.append(self.pre[-1] + x)  # pre[k] = sum of first k elements
    def sumRange(self, i, j):
        return self.pre[j+1] - self.pre[i]     # up to j, minus everything before i
# na = NumArray([-2,0,3,-5,2,-1])
# [na.sumRange(0,2), na.sumRange(2,5), na.sumRange(0,5)] -> [1, -1, -3]

Dry run

Building pre for nums = [-2, 0, 3, -5, 2, -1]:

Then the queries:

Complexity

• Time: O(n) to build, O(1) per query. The constructor walks the array once; each query reads two list entries and subtracts.
• Space: O(n). The prefix array holds n + 1 integers.

Edge cases and pitfalls

• Single-element range (i == j) works: pre[i+1] - pre[i] is just nums[i].
• Off-by-one is the classic bug. With the leading zero, the formula is pre[j+1] - pre[i], not pre[j] - pre[i] and not pre[j] - pre[i-1].
• Negative numbers are fine; prefix sums do not need non-negative input (unlike a sliding window).
• If the array could change, prefix sums break, because one update shifts every later prefix. That is LeetCode 307, which needs a Fenwick tree or segment tree.

Related problems

• Range Sum Query 2D - Immutable (LeetCode 304): the same idea extended to rectangles in a matrix.
• Find Pivot Index (LeetCode 724): compares the prefix sum on each side of an index.
• Subarray Sum Equals K (LeetCode 560): prefix sums plus a hash map to count ranges with a target sum.