Prefix Sum (Cumulative Sum Technique)

A prefix sum array pref stores cumulative totals so any contiguous range sum becomes two lookups: sum(L..R) = pref[R] - pref[L-1] with careful indexing—this is one of the most reused ideas in arrays and strings.

Why this shows up in the real world

Cashflow ledgers prefix into “balance so far” to answer “how much between April and June?” without rescanning every day. Image integral images in graphics prefix pixel blocks for fast filters. Genomic coverage tracks prefix counts along chromosomes to report depth in intervals.

Core idea (explained for students)

Build pref[i] = pref[i-1] + a[i] (or start pref[0]=a[0]). For inclusive range sums, pad with a zero sentinel at index -1 conceptually: define prefWith0 where prefWith0[0]=0 and prefWith0[i+1]=prefWith0[i]+a[i] so rangeSum(L,R)=prefWith0[R+1]-prefWith0[L]. Same pattern lifts to 2D prefix for rectangle sums.

Try this in Python

def range_sums(a: list[int], queries: list[tuple[int, int]]) -> list[int]:
    ps = [0]
    for x in a:
        ps.append(ps[-1] + x)
    return [ps[r + 1] - ps[l] for l, r in queries]


print(range_sums([1, 2, 3, 4, 5], [(1, 3), (0, 4)]))

Common mistakes

• Off-by-one when L = 0—that is why the extra zero column helps.
• Forgetting modulo subtraction: use (pref[R] - pref[L-1]) % MOD adjusted by + MOD if needed.
• Building prefix on a mutating array without recomputing when values change.

Key takeaways

• Prefix sums turn range sums into O(1) after O(n) prep.
• Pair with hash maps of prefix → index for subarray sum equals k problems.
• Write the sentinel version once and reuse everywhere.