Building a prefix sum

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

Store p[0]=0 and p[i+1]=p[i]+a[i]. A boundary-based array of length n+1 makes empty ranges and ranges starting at zero follow the same formula. The extra zero is a boundary before the first value, not an additional input element. Prefix values need not increase when input has negatives; range subtraction remains correct because it relies on cancellation rather than ordering.

Work through an example

For [2,-1,3], p=[0,2,1,4]. p[2]=1 summarizes indices 0 and 1; it does not include index 2.

Time and space complexity

Build Θ(n) time/Θ(n) storage; bounded arithmetic assumed.

Why it works

p[i] is exactly the sum of the first i elements.

Common mistakes

Omitting p[0] complicates boundary cases.
Prefix entries need a wide enough sum type.

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