Two-dimensional prefix sums

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

Two-dimensional prefixes use inclusion-exclusion. P[r+1][c+1]=a[r][c]+P[r][c+1]+P[r+1][c]-P[r][c], with a zero border. For rows [0,2) and columns [1,2) in the example, use P[2][2]-P[0][2]-P[2][1]+P[0][1]=10-0-4+0=6. A zero top/left border removes special branches for rectangles touching an outer edge.

Work through an example

For [[1,2],[3,4]], P=[[0,0,0],[0,1,3],[0,4,10]]. The right column is 10-4=6.

Time and space complexity

O(RC) build/storage and O(1) rectangle queries.

Why it works

P[r][c] summarizes rows before r and columns before c.

Common mistakes

Forgetting the add-back double-subtracts the overlap.
Row/column conventions must stay consistent.

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