Prefix Sum Basics (Cumulative Patterns)

Prefix sum basics are about building comfort with “how much so far?” arrays: the mental model of carrying a running total and freezing snapshots at each index.

Why this shows up in the real world

Loyalty points accumulate with each purchase; the receipt prints “points earned this trip” and “lifetime points”—that lifetime column is a prefix sum. Game XP bars fill cumulatively; designers balance quests knowing players see a monotone increasing curve.

Core idea (explained for students)

Given a, define pref[i] = sum(a[0..i]). Implement either with a simple loop or itertools.accumulate. Practice translating phrases like “balance after month i” into pref[i]. Recognize that subtracting two prefix snapshots isolates a window.

Try this in Python

from itertools import accumulate

a = [3, 1, 4, 1, 5]
pref = list(accumulate(a))
print(pref)

def window_sum(pref: list[int], L: int, R: int) -> int:
    return pref[R] if L == 0 else pref[R] - pref[L - 1]


print(window_sum(pref, 1, 3))

Common mistakes

• Starting loops at the wrong index so pref[0] never matches a[0].
• Confusing average so far (pref[i]/(i+1)) with prefix itself.
• Using floating accumulations where rounding breaks associativity—prefer integers or stable orders of operations.

Key takeaways

• Prefix is the discrete integral of your sequence.
• Always sketch tiny arrays (length 4) by hand before coding.
• Pair with difference arrays when updates are ranges.