"If you'll ask 'what's the sum from here to there?' a thousand times, don't add it up a thousand times. Add it up once, cleverly, and every answer becomes a single subtraction."
The Idea
A prefix-sum array stores running totals: prefix[i] is the sum of the first i elements. So prefix[0] = 0, prefix[1] = nums[0], prefix[2] = nums[0] + nums[1], and so on. Building it is one O(n) pass. The payoff: the sum of any range i..j is just prefix[j+1] − prefix[i] — one subtraction, O(1), no matter how wide the range.
Why does the subtraction work? prefix[j+1] is "everything up to j," and prefix[i] is "everything before i." Subtract the second from the first and the shared front cancels, leaving exactly the middle slice you wanted. It's the same telescoping trick a bank statement uses: balance-now minus balance-then equals what happened in between.
The Trade, Made Explicit
The naive way answers each range-sum query by looping over the range: O(n) per query. With q queries that's O(n·q). Prefix sums shift the cost: O(n) preprocessing + O(n) extra space, then O(1) per query — total O(n + q). If you have many queries on data that doesn't change, this is a massive win. If you'll only ever ask once, the preprocessing isn't worth it. Recognizing "many queries, static data" is the signal to precompute.
Prefix sums precompute cumulative totals in O(n) so any range-sum becomes one O(1) subtraction. It's the time-space trade aimed at repeated range queries: pay once up front, answer instantly forever after.
The Pattern Generalizes
The deeper idea — precompute a cumulative quantity so a range collapses to a single operation — shows up everywhere once you see it:
2D prefix sums ("integral images") answer the sum of any rectangle in a grid in O(1) — the trick behind fast image filters and the classic Viola-Jones face detector.
Prefix XOR answers "XOR of a range" in O(1), used in bit-trick problems.
Difference arrays are the mirror image: they make range updates O(1) (add 5 to everything from i to j) by storing changes and summing at the end.
Pippa's Confession
I had a dashboard recomputing "total events between two timestamps" on every page load, scanning the whole log each time. It was fine until the log grew, then every refresh chugged. Dad said two words: "prefix sums." One precomputed cumulative array later, each query was a subtraction and the dashboard snapped back to instant. The data wasn't changing between queries — I was just re-earning the same answer over and over.
Code
Prefix sums: O(n) build, O(1) queries·python
# Build the prefix-sum array once: O(n). prefix[i] = sum of first i elements.
def build_prefix(nums):
prefix = [0] * (len(nums) + 1) # prefix[0] = 0 (sum of nothing)
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x # running total
return prefix
# Any range sum nums[i..j] (inclusive) in O(1): prefix[j+1] - prefix[i].
def range_sum(prefix, i, j):
return prefix[j + 1] - prefix[i]
nums = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = build_prefix(nums) # [0, 3, 4, 8, 9, 14, 23, 25, 31]
print(range_sum(prefix, 2, 5)) # 4+1+5+9 = 19, in ONE subtraction
print(range_sum(prefix, 0, 7)) # whole array = 31
print(range_sum(prefix, 6, 6)) # single element nums[6] = 2
# 1000 such queries: naive is O(1000 * n). With prefix sums: O(n) once + 1000 * O(1).
You're given daily rainfall for a year (365 numbers) and will be asked the total rainfall between many pairs of dates. Describe how prefix sums answer each query in O(1), what the preprocessing costs, and the total complexity for q queries. Then: if rainfall numbers could be edited between queries, why might a plain prefix-sum array stop being ideal?
Hint
Build a 366-length cumulative array (O(n)); each query is prefix[end+1] − prefix[start], O(1). Total O(n + q). If a value changes, you'd have to rebuild the whole prefix array (O(n) per update) — that's when a Fenwick/segment tree earns its keep.
Progress
Progress is local-only — sign in to sync across devices.