Prefix sums with hashing

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

For current prefix s, earlier prefixes equal to s-target form target-sum subarrays. Count their multiplicity, then insert the current prefix; this avoids counting an empty subarray.

Work through an example

On [1,-1,1], target 1, the final prefix 1 sees two earlier zero prefixes. They represent [1,-1,1] and the final [1], giving three total matches.

Time and space complexity

Expected O(n) time/O(n) space; works with positive, zero, and negative values.

Why it works

seen contains counts of strictly earlier prefix boundaries.

Common mistakes

A set loses repeated-prefix counts.
Inserting before querying counts an empty range when target=0.

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