Range Sum Query — Immutable

This is the problem the whole pattern was invented for, and it is often the warm-up in a longer interview. The code is short. What the interviewer is really checking is whether you see that the queries are the expensive part, and whether you can say what breaks when the array stops being fixed.

Treat it as practice for the harder lessons that follow. The prefix array you build here is the same one that Subarray Sum Equals K walks with a hash map, and the same one that Range Sum Query 2D extends to a grid.

The problem

You are given a list of integers that will never change. Build an object that answers many questions of the form "what is the total of the elements from index left to index right, both included?"

• nums = [4, -2, 7, 1, -3, 6], query (0, 2) → 9, because 4 − 2 + 7 = 9.
• Same array, query (2, 5) → 11, because 7 + 1 − 3 + 6 = 11.
• Same array, query (1, 1) → -2, a range of one element.

Constraints: 1 ≤ n ≤ 10⁵, values between −10⁵ and 10⁵, up to 10⁵ queries, and every query has 0 ≤ left ≤ right < n.

Clarifying questions

• Are both ends included? Yes. (This decides the + 1 in the formula.)
• Can the array change between queries? No — "immutable". This is the question that decides the whole design.
• Are queries always valid? Assume yes: left ≤ right, both in range.
• Can values be negative? Yes. That rules out any trick that assumes sums only grow.
• How many queries compared with n? Up to 10⁵ each. That number is the reason to precompute.

Approach 1: the simple way

Store the array, and for each query add up the elements in the range.

1class NumArrayBrute:2    """Answers each query by adding up the range."""34    def __init__(self, nums: list[int]) -> None:5        self.nums = nums67    def sum_range(self, left: int, right: int) -> int:8        """Sum of nums[left..right], inclusive."""9        total = 010        for i in range(left, right + 1):11            total += self.nums[i]12        return total

Construction is O(1). Each query costs O(right − left + 1), which is O(n) in the worst case. Space is O(1) beyond the input.

Why it is too slow: with n = 10⁵ and 10⁵ queries that each cover most of the array, the total is about 10⁵ × 10⁵ = 10¹⁰ additions. At roughly 10⁷ simple Python operations per second, that is over 15 minutes. Even the average case — ranges of about n/3 elements — is over 3 × 10⁹.

The key insight

Two queries that overlap repeat work. (0, 50000) and (0, 50001) share 50,001 additions, and the loop throws the first result away before doing the second.

Every range sum is the difference of two "sums from the start". The sum from left to right is (everything up to right) minus (everything before left). There are only n + 1 possible "sums from the start", so compute all of them once, in the constructor, and each query becomes one subtraction.

This moves the cost from the part that happens 10⁵ times (queries) to the part that happens once (construction). That trade — pay once up front, answer every question cheaply — is the whole pattern.

Approach 2: prefix sums

1. In the constructor, build prefix of length n + 1 with prefix[0] = 0.
2. Fill it left to right: prefix[k + 1] = prefix[k] + nums[k].
3. For a query, return prefix[right + 1] - prefix[left].

1class NumArray:2    """Answers range-sum queries on a fixed array in O(1) each."""34    def __init__(self, nums: list[int]) -> None:5        self.prefix = [0] * (len(nums) + 1)6        for k, value in enumerate(nums):7            self.prefix[k + 1] = self.prefix[k] + value89    def sum_range(self, left: int, right: int) -> int:10        """Sum of nums[left..right], inclusive."""11        return self.prefix[right + 1] - self.prefix[left]

Dry run: building the prefix array

For nums = [4, -2, 7, 1, -3, 6]:

So prefix = [0, 4, 2, 9, 10, 7, 13]. Notice it goes down twice — at index 1 and index 4 — because those elements are negative.

Dry run: answering the queries

All four match adding the elements by hand.

Complexity. Construction is O(n) time — one addition per element. Each query is O(1) — two lookups and a subtraction. Space is O(n) for the prefix array. For 10⁵ elements and 10⁵ queries, that is about 2 × 10⁵ operations instead of 10¹⁰.

Edge cases

• A range that starts at 0. prefix[right + 1] - prefix[0] works because prefix[0] = 0 is stored. Without the leading zero you would need an if left == 0 branch.
• A single element. (i, i) returns prefix[i + 1] - prefix[i], which is exactly nums[i]. Use it as your self-test.
• The whole array. (0, n − 1) returns prefix[n], the grand total.
• Negative totals. Nothing in the formula assumes sums are positive; (1, 1) above returns −2 correctly.
• An empty array. The constructor builds [0] and there are no valid queries, so nothing breaks.

Saying it in the interview

Follow-ups

"What if the array can be updated?" A prefix array goes stale on every update, and rebuilding it is O(n). Use a Fenwick tree (binary indexed tree): both updates and prefix sums cost O(log n).

1class FenwickTree:2    """Point updates and prefix sums, both in O(log n)."""34    def __init__(self, nums: list[int]) -> None:5        self.n = len(nums)6        self.tree = [0] * (self.n + 1)7        self.nums = [0] * self.n8        for i, value in enumerate(nums):9            self.update(i, value)1011    def update(self, i: int, value: int) -> None:12        """Set nums[i] = value."""13        delta = value - self.nums[i]14        self.nums[i] = value15        k = i + 116        while k <= self.n:17            self.tree[k] += delta18            k += k & -k                 # jump to the next node that covers k1920    def prefix(self, k: int) -> int:21        """Sum of the first k elements."""22        total = 023        while k > 0:24            total += self.tree[k]25            k -= k & -k                 # drop the lowest set bit26        return total2728    def sum_range(self, left: int, right: int) -> int:29        """Sum of nums[left..right], inclusive."""30        return self.prefix(right + 1) - self.prefix(left)

Each slot tree[k] holds the sum of a block of elements whose length is the lowest set bit of k. A prefix query adds O(log n) blocks; an update touches O(log n) blocks. On our example, sum_range(2, 5) is 11; after update(3, 10) it becomes 20. Construction as written is O(n log n). Naming the Fenwick tree and its costs usually earns the point even if you are not asked to code it.

"What if there are many range updates and one read at the end?" Use a difference array: O(1) per update, then one O(n) prefix pass (see the core idea lesson).

"What if it is a grid?" Use a 2D prefix table — that is the Range Sum Query 2D lesson in this section.