Range Sum Query - Immutable
Problem statement
You're given an integer array nums that never changes after it's built.
Implement a class NumArray that answers many range-sum queries against it
efficiently:
NumArray(nums)builds the object from the array.sumRange(left, right)returns the sum ofnums[left]throughnums[right], inclusive — and may be called many times.
Examples
Example 1
Input: ["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output: [null, 1, -1, -3]
Explanation: The array is nums = [-2, 0, 3, -5, 2, -1].
Hints
sumRange call repeats
the same additions across many calls — do some of that work once, in the
constructor, instead.Approach
Optimal: Precompute a prefix sum once
Intuition
Do the repeated work exactly once, up front. Build a prefix array where
prefix[i] holds the sum of everything in nums before index i
(prefix[0] is 0, since there's nothing before index 0). Once that
exists, the sum of any range [left, right] is just "everything up to
right" minus "everything before left" — one subtraction, however wide the
range is. That's what turns every future query into O(1).
Steps
- In the constructor, build
prefixwith one extra slot at the front:prefix[0] = 0, andprefix[i + 1] = prefix[i] + nums[i]for eachi. - In
sumRange(left, right):- Return
prefix[right + 1] - prefix[left].
- Return
Dry run
Building the prefix array for nums = [-2, 0, 3, -5, 2, -1]:
| i | nums[i] |
prefix[i] before |
prefix[i+1] after |
|---|---|---|---|
| 0 | -2 | 0 | -2 |
| 1 | 0 | -2 | -2 |
| 2 | 3 | -2 | 1 |
| 3 | -5 | 1 | -4 |
| 4 | 2 | -4 | -2 |
| 5 | -1 | -2 | -3 |
So prefix = [0, -2, -2, 1, -4, -2, -3]. Now every query is one subtraction:
| call | calculation | result |
|---|---|---|
sumRange(0, 2) |
prefix[3] - prefix[0] = 1 - 0 |
1 |
sumRange(2, 5) |
prefix[6] - prefix[2] = -3 - (-2) |
-1 |
sumRange(0, 5) |
prefix[6] - prefix[0] = -3 - 0 |
-3 |
All three match the example's expected output, and none of them re-scanned
nums at all.
Edge cases: sumRange(0, n - 1) — the whole array — is
prefix[n] - prefix[0], which is just the array's total sum. The extra 0
at the front of prefix means left = 0 never needs a special case.
Complexity
Time O(n) - once, in the constructor, to build the prefix array. Every `sumRange` call afterward is O(1) — a single subtraction, no matter how wide the range is. Across `q` queries, the total work is O(n + q) instead of the brute force's O(n · q) worst case.
Space O(n) - one extra array of `n + 1` running totals.
class NumArray:
def __init__(self, nums: list[int]):
n = len(nums)
self.prefix = [0] * (n + 1)
for i in range(n):
self.prefix[i + 1] = self.prefix[i] + nums[i]
def sumRange(self, left: int, right: int) -> int:
return self.prefix[right + 1] - self.prefix[left]
if __name__ == "__main__":
numArray = NumArray([-2, 0, 3, -5, 2, -1])
print(numArray.sumRange(0, 2)) # 1
print(numArray.sumRange(2, 5)) # -1
print(numArray.sumRange(0, 5)) # -3RecapThe whole problem in a few lines, for the night before
- Spot it: many repeated "sum of a range" queries against an array that never changes
- Idea: precompute a prefix sum once;
sumRange(l, r) = prefix[r+1] - prefix[l] - Cost: O(n) time and space to build, O(1) time per query after that
- Trap: summing the range from scratch on every call works but costs O(n) per query — fine for a few calls, too slow across many
- Remember: if the array can be updated later, this trick breaks — that's Range Sum Query - Mutable, solved with a Fenwick tree instead
Interview follow-ups
What if
numscould also be updated —update(index, val)— between queries?That's a different problem, Range Sum Query - Mutable: a plain prefix array breaks, because a single update would require rebuilding every prefix sum after that index. A Fenwick tree (binary indexed tree) or segment tree keeps both updates and range-sum queries at O(log n) each instead.
What if the queries were over a 2D grid instead of a 1D array?
Build a 2D prefix sum, where
prefix[i][j]holds the total of the rectangle from(0, 0)to(i - 1, j - 1). Any sub-rectangle's sum is then found with inclusion-exclusion over its four corners — this is exactly Range Sum Query 2D - Immutable.The array is too large to fit in memory. How would you adapt this?
Split it into fixed-size chunks, and keep only each chunk's total in memory. A query's range typically spans some full chunks (use their precomputed totals) plus a partial chunk at each end (scan just those directly from storage). This trades a little more work per query for memory that no longer has to hold the entire array or its full prefix sum.
Frequently asked questions
Because nums never changes after the object is built — that's exactly what
makes the prefix-sum trick safe. If an element could change later, the
precomputed prefix array would go stale for every index after it. The
mutable version of this problem, Range Sum Query - Mutable, needs a
different structure (a Fenwick tree or segment tree) precisely because
updates would break a plain prefix array.
The extra 0 at the front means prefix[i] always means "the sum of
everything strictly before index i", even when i is 0. Without it,
sumRange(0, right) would need a special case to avoid looking at
prefix[-1].
Dashboards and reports often need many repeated "sum over a time range" queries against a metrics window that has already been collected and won't change — total bytes served between two timestamps, total errors between two deploys. Precomputing running totals once instead of rescanning the data on every query is the same idea behind time-series rollups.
When sumRange is only called a handful of times, or the ranges asked for
are always small, the O(n) upfront cost of building a prefix array may not be
worth paying. The brute force is the simplest correct choice when queries are
rare.