Lesson 9 — Prefix sums

Prefix sums: precompute once, answer instantly

A prefix sum list stores running totals: pre[k] is the sum of the first k items. Building it takes one pass. After that, the sum of any range a[i..j] is just pre[j + 1] − pre[i] — one subtraction, no loop.

a   = [2, 4, 6]
pre = [0, 2, 6, 12]
# sum of a[1..2] = pre[3] - pre[1] = 12 - 2 = 10

Why it matters: if you must answer thousands of "sum from day i to day j" questions, this turns each answer from O(n) into O(1) (one step).