Prefix sums

Store running totals so a range sum can be found by subtracting two totals.

Remember: Range = end total − start total.

Example: [3,-2,5] → prefix [0,3,1,6]; sum[1,3) = 6−3 = 3.

Time: O(n) build. Auxiliary space: O(n).

Formula: sum[l, r) = prefix[r] − prefix[l]

prefix[0] = 0. The prefix array has n + 1 entries; queries take O(1).

Complexities describe the underlying algorithm; tutorial snapshots and rendering can use additional resources.

The interactive workspace loads here when JavaScript is available. You can still browse the learning notes and links above without it.