Skip to main content
DSA patterns

Range Sum Query - Immutable

easyPrefix sum Must-doCloudflareDatadogSplunk

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 of nums[left] through nums[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

Hint 1: Recomputing a range's sum from scratch on every 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

  1. In the constructor, build prefix with one extra slot at the front: prefix[0] = 0, and prefix[i + 1] = prefix[i] + nums[i] for each i.
  2. In sumRange(left, right):
    • Return prefix[right + 1] - prefix[left].

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))   # -3
RecapThe 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 nums could 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.