Difference arrays and range updates

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

A difference array records changes at boundaries. Adding delta to [l,r) writes diff[l]+=delta and diff[r]-=delta; a final prefix scan reconstructs all values.

Work through an example

For five zeros, add 3 to [1,4): diff=[0,3,0,0,-3,0]. Reconstruction gives [0,3,3,3,0].

Time and space complexity

O(1) per batched range update and O(n) reconstruction; Θ(n) storage.

Why it works

The running sum of differences equals the accumulated update at the current position.

Common mistakes

Allocate an n+1 sentinel for right=n.
Difference arrays do not directly support arbitrary online queries.

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