Prefix & Suffix Running Totals
Precomputing cumulative values to answer range questions instantly — the trick behind Product of Array Except Self.
A prefix sum is a running total: prefix[i] holds the sum of everything before index i, with prefix[0] = 0 as a sentinel. Build it once in O(n), and any range sum collapses to a single subtraction: sum(i..j) = prefix[j+1] − prefix[i]. Everything up to j, minus everything before i, leaves exactly the slice you asked about.
The animation shows a wave sweeping left to right, filling a prefix row beneath the raw array — each cell is the previous cell plus the value above it. Then a query drops brackets onto positions i and j, the two relevant prefix cells light up, and an equation banner animates prefix[j+1] − prefix[i] = answer.
What to watch for:
- The sentinel zero. Because prefix[0] = 0 and the row has n+1 cells, ranges starting at index 0 need no special case — the same subtraction works everywhere.
- Pay once, answer forever. One O(n) build, then every range query is O(1). Ten queries or ten million — the prefix row never needs rebuilding.
- The idea generalizes. Swap addition for multiplication and you get prefix and suffix products — combine "product of everything left of i" with "product of everything right of i" and you've solved Product of Array Except Self without division.