303. Range Sum Query – Immutable

303

EasyPrefix Sum and Difference ArrayPrefix sum arrayPrecomputed prefix sums

Range Sum Query – Immutable

Design a NumArray class that is initialized once with an integer array nums and then answers many range-sum queries. sumRange(left, right) must return the sum of the elements nums[left..right] inclusive. Queries may be called many times, so each one should be fast.

Open official problem prompt ↗

In plain English

Answer arbitrary range-sum questions on a fixed array instantly, no matter how many times we are asked.

Picture it like this

Think of running mile markers on a highway. To find the distance between exit 12 and exit 30 you do not re-drive the road; you subtract marker 12 from marker 30. Prefix sums are those mile markers for the array.

Example

Input: NumArray([-2, 0, 3, -5, 2, -1]); sumRange(0, 2)
Output: 1
Why: nums[0] + nums[1] + nums[2] = -2 + 0 + 3 = 1

Constraints

1 <= nums.length <= 10^4-10^5 <= nums[i] <= 10^50 <= left <= right < nums.lengthAt most 10^4 calls to sumRange

Pattern lesson

See the pattern, then code

Precomputed prefix sums

↗

Prefix Sum and Difference Array

Repeated range queries, subarray totals, balanced counts, or batched range updates.. If pre[i] holds the sum of the first i elements, then any range sum nums[left..right] is just pre[right+1] - pre[left]; the shared prefix cancels out.

New words, made simpleKnow these before the algorithm

Prefix sum: pre[i] = sum of the first i elements, so pre[0] is 0 and pre[n] is the total.
Immutable: The array never changes after construction, which is what lets a one-time precomputation stay valid.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Sum on every query

With up to 10^4 queries on a length-10^4 array this becomes 10^8 operations; wasteful when the array is fixed.

For each sumRange call, loop from left to right adding elements.

Time O(n) per querySpace O(1)

Best choicePrefix sums

Turns every query into constant time, which is the whole point of the immutable design.

Precompute cumulative sums once, then answer each query with a single subtraction.

Time O(n) build, O(1) querySpace O(n)

The rule we keep true

Invariant

pre[i] always equals the sum of nums[0..i-1], so pre[right+1] - pre[left] is exactly the sum of nums[left..right].

Why this is correct

Reasoning

The sum of the first right+1 elements minus the sum of the first left elements leaves precisely the elements from index left through right, because the overlapping prefix is subtracted away.

The algorithm in three movesSay these aloud before coding

1In the constructor, build pre where pre[0] = 0 and pre[i+1] = pre[i] + nums[i]

pre = [0, -2, -2, 1, -4, -2, -3]

2Store pre on the instance

sumRange(0,2) = pre[3] - pre[0]

3For each query return pre[right + 1] - pre[left]

= 1 - 0 = 1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

-21

-22

-44

-25

-36

1 · Readnums = [-2,0,3,-5,2,-1]

2 · AskWhat is each cumulative total?

3 · Update statepre = [0,-2,-2,1,-4,-2,-3]

4 · ResultPrefix array ready

Key takeaway

The prefix array pre; the query subtracts pre[0] from pre[3] to get the sum of indices 0..2.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-5Constructor builds prefix sums
Allocate one extra slot so index shifting is clean, then fill each pre[i+1] from the previous total.
2
Lines 7-8Constant-time query
A single subtraction yields the range sum; no loop is needed at query time.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single-element range where left == right returns just that element
Querying the whole array (0, n-1) returns pre[n]
Negative numbers are handled naturally since sums can decrease

Common beginner mistakes

Off-by-one: sumRange must use pre[right+1], not pre[right]
Recomputing prefix sums inside sumRange instead of the constructor, which throws away the O(1) benefit
Forgetting the leading zero in pre, which breaks the left == 0 case

Check your understanding

Why does the prefix array have length n+1 instead of n?

Range Sum Query – Immutable

Range Sum Query – Immutable

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Prefix Sum and Difference Array