prefix-sum speed-ups

Imagine you keep getting asked 'what is the total of the array between position i and position j?' If you add up the slice from scratch each time, a single query costs up to O(n), and many queries become slow. A prefix sum is a one-time preparation that makes every such range-total query answerable in O(1). It is the simplest and most ubiquitous DP speed-up: precompute running totals once, then answer infinitely many range questions by subtraction.

Build an array P where P[0] = 0 and P[k] = a[1] + a[2] + ... + a[k], the sum of the first k elements. Each P[k] is just P[k-1] + a[k], so the whole prefix-sum array is filled in one O(n) pass — itself a tiny DP with the recurrence P[k] = P[k-1] + a[k]. Now the sum of any contiguous range a[i..j] equals P[j] - P[i-1]: the running total up to j, minus the running total up to just before i, leaves exactly the middle chunk. That subtraction is O(1) regardless of how wide the range is. The same idea extends to two dimensions (a 2D prefix sum answers rectangle-sum queries with four lookups via inclusion-exclusion) and to other invertible operations.

Where this transforms a DP is in transitions that sum over a contiguous range of previous states. If dp[i] = (some function of) the sum of dp[j] for j in a window, naively each i costs O(window) and the DP is O(n times window) or O(n^2); a prefix sum over the dp values collapses each transition to O(1), often turning O(n^2) into O(n). The honest limits: prefix sums require an invertible combine — sums and XOR work because you can subtract or cancel, but plain max does NOT (you cannot un-take a maximum), so range-max needs a different structure like a sparse table or segment tree. Also, prefix sums assume a static array; if the underlying values change between queries, a plain prefix sum goes stale and you need a Fenwick tree or segment tree instead.