Prefix sums

Prefix sums

Dashboards, banks, and analytics systems answer the same query shape thousands of times a day: what is the total between day lo and day hi? Re-adding the slice costs O(n) per query, so q queries cost O(n·q) — the same recompute-from-scratch disease the sliding window cured, except the ranges here are arbitrary, not a fixed-size window sliding by one.

The fix is a prefix sum array: prefix[i] = the sum of the first i elements, with prefix[0] = 0. Build it once in O(n). Then any range total falls out of one subtraction:

sum of nums[lo..hi] = prefix[hi + 1] - prefix[lo]

because prefix[hi + 1] counts everything up through index hi, and subtracting prefix[lo] removes everything before lo. Build once, answer every range query in O(1).

The off-by-one is deliberate: making prefix one cell longer than nums, with that leading 0, lets ranges that start at index 0 use the same subtraction — no special case.

Prefix sums + a dictionary: subarray sums

The famous interview follow-up: how many contiguous runs (subarrays) sum to exactly k? Checking every (lo, hi) pair is O(n²). Prefix sums turn it into lesson 1-1's pair-sum trick.

A subarray from lo to hi sums to k exactly when prefix[hi + 1] - prefix[lo] = k — that is, when some earlier prefix value equals current prefix - k. So walk left to right with a running prefix total and a dictionary counting each prefix value seen so far; at every position, add seen[running - k] to the answer.

Seed the dictionary with {0: 1} — the empty prefix — so runs that start at index 0 are counted. One pass, O(n) time. And unlike a sliding window, this handles negative numbers, because it never assumes that growing the window grows the sum.