Module 06 · Prefix Sums, Prefix State, and Difference Arrays

052. Answer Static Range-Sum Queries

Foundation · Download this solution · All solutions and shared helpers

Problem

Given integers nums and valid queries (left,right) satisfying 0<=left<=right<=n, return each sum over nums[left:right]. Queries use half-open boundaries and may be empty. Preprocess once; answer each query in constant time.

Examples

Example 1

range_sums([2, -1, 3, 4], [(1, 3), (0, 4), (2, 2)])
=> [2, 8, 0]

The first range contains -1 and 3; the last is empty.

Example 2

range_sums([], [(0, 0)])
=> [0]

The empty array still supports its empty range.

Example 3

range_sums([5], [])
=> []

No queries require no answers.

Reveal the worked solution and reasoning

Why this mechanism works

The prefix through right contains the desired range plus everything before left. Subtracting the prefix through left cancels that unwanted part, regardless of signs. Reusing one prefix list amortizes preprocessing over all queries.

State and boundaries

prefix[i] is the sum before index i. Each query reads two immutable boundary values.

Protocol

Build a leading-zero prefix array.
For each query subtract prefix[left] from prefix[right].
Preserve query order in the output.

Visualization

prefix[right] = before-left + requested range
prefix[left]  = before-left
subtract      = requested range

Python implementation

def range_sums(nums, queries):
    prefix = [0]
    for value in nums:
        prefix.append(prefix[-1] + value)
    return [prefix[right] - prefix[left] for left, right in queries]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

range_sums([2, -1, 3, 4], [(1, 3), (0, 4), (2, 2)])

L2 range_sums: prefix = [0]
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0]

L3 range_sums: for value in nums:
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0]; value=2

L4 range_sums: prefix.append(prefix[-1] + value)
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0, 2]; value=2

L3 range_sums: for value in nums:
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0, 2]; value=-1

L4 range_sums: prefix.append(prefix[-1] + value)
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0, 2, 1]; value=-1

L3 range_sums: for value in nums:
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0, 2, 1]; value=3

L4 range_sums: prefix.append(prefix[-1] + value)
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0, 2, 1, 4]; value=3

L3 range_sums: for value in nums:
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0, 2, 1, 4]; value=4

... 1 intermediate state changes omitted ...

L5 range_sums: return [prefix[right] - prefix[left] for left, right in queries]
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0, 2, 1, 4, 8]; value=4; left=1; right=3

L5 range_sums: return [prefix[right] - prefix[left] for left, right in queries]
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0, 2, 1, 4, 8]; value=4; left=0; right=4

L5 range_sums: return [prefix[right] - prefix[left] for left, right in queries]
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0, 2, 1, 4, 8]; value=4; left=2; right=2

L5 range_sums: return [prefix[right] - prefix[left] for left, right in queries]
nums=[2, -1, 3, 4]; queries=[(1, 3), (0, 4), (2, 2)]; prefix=[0, 2, 1, 4, 8]; value=4

Result: [2, 8, 0]. The first range contains -1 and 3; the last is empty.

range_sums([], [(0, 0)])

L2 range_sums: prefix = [0]
nums=[]; queries=[(0, 0)]; prefix=[0]

L5 range_sums: return [prefix[right] - prefix[left] for left, right in queries]
nums=[]; queries=[(0, 0)]; prefix=[0]; left=0; right=0

L5 range_sums: return [prefix[right] - prefix[left] for left, right in queries]
nums=[]; queries=[(0, 0)]; prefix=[0]

Result: [0]. The empty array still supports its empty range.

Why the solution is correct

Both prefix values include exactly the same positions before left, so subtraction cancels them. Positions from left through right-1 occur only in the larger prefix expression and remain once. Equal boundaries therefore yield zero.

Time and space

O(n+q) time and O(n+q) space including q answers; each query is O(1) after preprocessing.

Common mistakes

Using right+1 would reinterpret the query as inclusive. Rebuilding the prefix per query defeats the intended preprocessing benefit.

Reasoning card

State: prefix[i] is the sum before index i. Each query reads two immutable boundary values.

Invariant: prefix[right]-prefix[left] equals the requested range.

Decision to rehearse: Subtract cumulative boundaries.

Finish: Preserve query order in the output

Transfer exercise

Allow point updates between queries. Explain why a fixed prefix list becomes stale and what a Fenwick tree would change.