Prefix Sums

Prefix sums turn repeated range-sum queries into constant-time work. One pass over the array writes a running total, prefix[k] = nums[0] + … + nums[k − 1]; after that, the sum of any contiguous range nums[l..r] is prefix[r + 1] − prefix[l]. That is two reads and one subtraction, whether the range covers one cell or the whole array.

Think of the odometer on a road trip. Write down the reading at every town, and you never re-drive a stretch to learn how long it is: the distance from town 2 to town 6 is one reading minus another. Prefix sums do the same for an array. The work moves out of the question and into one bookkeeping pass done up front.

How Prefix Sums Work

Picture a fence between every pair of neighbouring cells, plus one before the first cell and one after the last. An array of n values has n + 1 fences, numbered 0 to n. Then prefix[k] is the total of everything left of fence k. Fence 0 has nothing to its left, so prefix[0] = 0, and prefix[n] is the sum of the whole array.

Building the array is one loop. Each entry is the previous entry plus the cell that just passed: prefix[k] = prefix[k − 1] + nums[k − 1]. That is n additions, done once.

A query for nums[l..r], inclusive on both ends, needs the two fences that bracket the range: fence l sits just before nums[l], and fence r + 1 sits just after nums[r]. Everything left of fence r + 1, minus everything left of fence l, leaves exactly the range. The shared part nums[0..l − 1] cancels. The query is one line with no loop, and its cost does not depend on r − l.

The leading zero earns its slot. Without prefix[0] = 0, a query that starts at l = 0 would have nothing to subtract and would need its own branch. With it, sum(0..r) = prefix[r + 1] − prefix[0] falls out of the same formula.

The trick does not care about signs. Negative values just make the running total dip; the subtraction still cancels the shared part exactly. The greedy shrink in the minimum-length Sliding Window lesson relies on non-negative values. Fixed-length sliding windows do not have that restriction; prefix sums also work with signed values.

The price shows up when the array changes. Every prefix[k] with k > i includes nums[i], so changing one value makes all n − i later entries stale. Each must be shifted by the same delta = new − old before the next query can trust the row.

Prefix Sums Step by Step

The default input is nums = [3, 1, 4, -2, 5, 9, 2, 6] with four queries: sum(2..5), sum(0..7), sum(4..4) and sum(1..6).

Start with the question. What is sum(2..5)? Reading 4, −2, 5 and 9 one by one gives running totals 4 → 2 → 7 → 16: four reads. Now ask for sum(0..7). A direct sum starts another scan. The prefix table stores work you can reuse between queries. The opening scan demonstrates the direct method; the comparison below uses the four queries on the same array.

Build. Start with prefix[0] = 0, then add one cell per step:

1. prefix[1] = 0 + 3 = 3
2. prefix[2] = 3 + 1 = 4
3. prefix[3] = 4 + 4 = 8
4. prefix[4] = 8 + (−2) = 6. The total dips; nothing breaks.
5. prefix[5] = 6 + 5 = 11
6. Steps 6–8 continue the same way: 20, 22, 28.

The finished row is prefix = [0, 3, 4, 8, 6, 11, 20, 22, 28], built with 8 additions.

Query. Each query reads two entries:

1. sum(2..5) = prefix[6] − prefix[2] = 20 − 4 = 16. Summing directly would read 4 cells.
2. sum(0..7) = prefix[8] − prefix[0] = 28 − 0 = 28. The whole array, still 2 reads; this is where the leading zero pays off.
3. sum(4..4) = prefix[5] − prefix[4] = 11 − 6 = 5. A single cell, still 2 reads.
4. sum(1..6) = prefix[7] − prefix[1] = 22 − 3 = 19. Six cells, 2 reads.

Summing each range directly would read 4 + 8 + 1 + 6 = 19 cells. The prefix version reads 8 entries for the queries, plus the 8 additions it spent once on the build.

On the canvas, prefix[k] sits below fence k. The first two additions keep the old total and the incoming value in focus together. The first query then reads the right total, reads the left total, and cancels the cells they share before holding the answer. The bars mark covered positions, not numerical magnitude: a long span can still sum to 0. Later queries repeat the same rule more quickly. At the bottom, prefix reads stays at 2 while direct reads changes from 4 to 8 to 1 to 6.

Load the Point update scenario to see the other side. After sum(0..5) = 20, nums[1] changes from 1 to 7 (Δ = +6). The entries prefix[2..8] turn stale, and the repair loop rewrites all seven of them before the same query, asked again, returns 26.

Time and Space Complexity

Space is O(n) for the n + 1 prefix entries. Repeated long-range queries on a mostly unchanged array can repay the initial build. A single-cell query already needs only one direct read, so two prefix reads are not automatically cheaper. With q queries on a fixed array, the total time complexity is O(n + q) instead of O(n · q) in the worst case.

When updates are frequent, a plain prefix array is the wrong tool. A Fenwick tree (binary indexed tree) or a segment tree answers range sums and point updates in O(log n) each. The lesson animates the plain array so the update cost is visible rather than hidden.

Edge Cases

• Range starting at index 0. sum(0..r) = prefix[r + 1] − prefix[0], and prefix[0] = 0. No special branch.
• Single-cell range. sum(i..i) = prefix[i + 1] − prefix[i] = nums[i]. Still two reads.
• The whole array. sum(0..n − 1) = prefix[n]. The last entry holds the grand total.
• Negative values. Totals can fall as well as rise; answers stay exact. The default run dips from 8 to 6.
• Equal prefix values. If prefix[a] = prefix[b], the range nums[a..b − 1] sums to 0. The Equal totals scenario shows three such ranges in one array, which is the starting point for "count subarrays that sum to k".
• Update at the first or last index. Changing nums[0] rewrites all n later entries; changing nums[n − 1] rewrites only prefix[n].

Common Mistakes

• Using prefix[r] − prefix[l] for an inclusive range. That drops nums[r]. The right fence of nums[l..r] is r + 1, which is why the prefix array has n + 1 entries.
• Storing the sum through nums[k] with no leading zero. The array is one entry shorter and every l = 0 query needs an if. Off-by-one bugs tend to collect around that branch.
• Rebuilding inside the query. Calling build(nums) once per query, or summing nums[l:r + 1] in the loop, brings back O(n) per query. Build once, reuse the array.
• Forgetting the array is a snapshot. After nums[i] changes, every prefix[k] with k > i is stale. Either repair them all with prefix[k] += delta or switch to a Fenwick tree.
• Ignoring overflow on long inputs. In languages with fixed-width integers, the running total can exceed the type even when every single value fits. Use a wider type for the prefix array.