Range sum queries

What is a prefix sum?

A prefix is the beginning of a sequence. A prefix-sum array stores totals from the beginning up to each boundary. Once these totals exist, subtracting two of them gives the sum of a range without adding every item in that range again. A difference array is a related way to record where range changes start and stop.

Example: For [2, 3, 4], store prefix totals [0, 2, 5, 9]. The total of positions 1 through 2 is 9 − 2 = 7.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays Hash maps and sets

Understand the idea

Subtract the prefix before a range from the prefix at its end. For [l,r), answer=p[r]-p[l]. For inclusive [l,r], use p[r+1]-p[l]. Repeated queries benefit from paying the preprocessing cost once. For q queries the total is O(n+q), compared with O(nq) for independently scanning potentially full-length ranges. The original values can remain unchanged.

Work through an example

The range [1,3) in [2,-1,3] sums to p[3]-p[1]=4-2=2. Empty [2,2) gives zero.

Time and space complexity

O(1) query after O(n) preprocessing; changing an element invalidates later prefixes.

Why it works

The common prefix cancels, leaving exactly the requested interval.

Common mistakes

Do not mix inclusive and half-open endpoints.
Static prefixes are unsuitable for many interleaved updates.

Chapter lab · Python implementation

Prefix sums summarize everything before a boundary. We use half-open ranges [left,right): they include left and exclude right. The lab combines cumulative sums with a frequency map to count subarrays, including negative values that make ordinary sum-based sliding windows unreliable.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def prefix(values):
    result=[0]
    for x in values:
        result.append(result[-1]+x)
    return result

def range_sum(p,left,right):
    if not 0<=left<=right<len(p):
        raise ValueError('invalid half-open range')
    return p[right]-p[left]

def count_target(values,target):
    seen={0:1}
    total=answer=0
    for x in values:
        total+=x
        answer+=seen.get(total-target,0)
        seen[total]=seen.get(total,0)+1
    return answer

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

p=prefix([2,-1,3]); assert p==[0,2,1,4]
assert range_sum(p,1,3)==2
assert range_sum(p,2,2)==0
assert count_target([1,-1,1],1)==3
assert count_target([0,0],0)==3
assert count_target([],0)==0

CHECK YOUR UNDERSTANDING