Segment Tree vs Prefix Sum Array: When the O(log n) Query Is Worth It

A prefix sum array answers “what is the sum of a[l..r]?” with two array reads and a subtraction. Nothing beats that. The cost shows up the moment a[i] changes: every prefix from i to the end is now wrong, so an update is O(n).

A segment tree trades that away. Queries become O(log n) instead of O(1), and updates drop from O(n) to O(log n). That trade is the entire decision, and you can settle it with arithmetic rather than instinct — plus one structural reason that has nothing to do with updates at all.

The crossover is arithmetic, not instinct

Write down three numbers: n (array length), Q (range queries), U (point updates), with queries and updates interleaved so you cannot batch.

A prefix sum array pays roughly n/2 writes per update (rebuild the suffix from the changed index) and about 2 reads per query. A segment tree pays about log2(n) node writes per update and up to 2 * log2(n) node visits per query, because a range query walks two boundary paths down the tree.

At n = 1,000,000, log2(n) is about 20:

• Prefix sum update: ~500,000 writes
• Segment tree update: ~20 writes
• Segment tree query: ~40 node visits

One prefix-sum update costs about as much as 12,500 segment tree operations. Setting the totals equal gives U * 500000 < 40 * (Q + U), which simplifies to roughly U < Q / 12500. At a million elements, prefix sums only stay ahead if fewer than one in twelve thousand operations is a write. Almost no real workload is that read-skewed.

Run the same math at n = 1000 and the picture flips. log2(1000) is about 10, so a prefix update costs ~500 writes against ~20 for the tree, and the break-even lands near one update per 24 queries. That is a threshold real workloads cross in both directions.

The formula also ignores memory hierarchy, and at small n that matters more than the exponents. Rebuilding a 1,000-element prefix suffix is a contiguous forward loop the compiler will vectorize and the prefetcher will feed. A segment tree query touches ~20 nodes scattered across the array with data-dependent indices — branchy, harder to prefetch. Below a few thousand elements, treat the crossover as “measure it,” not “the tree wins.”

What a segment tree actually stores

Each node holds the answer for a contiguous range. The root covers [0, n), each internal node splits its range in half, and each leaf holds one element. A query for [l, r) decomposes into at most 2 * ceil(log2(n)) of these canonical nodes, and you merge their stored answers.

The merge function only has to be associative. Sum, min, max, gcd, bitwise AND/OR, matrix product, “minimum value plus how many times it occurs” — all fine.

A prefix sum array needs something stronger: an invertible operation, because it computes range = P[r] - P[l]. Min has no inverse. There is no prefix-min array that answers an arbitrary range min, no matter how much preprocessing you throw at it. So the second reason to reach for a segment tree is that your operation simply cannot be decomposed by subtraction — and that reason applies even if the array never changes.

Here is the shape of the whole family:

Read that table as a decision procedure. Static plus invertible: prefix array. Static plus idempotent: sparse table, and you keep the O(1) query. Dynamic plus invertible sums only: Fenwick tree, which is roughly a third of the code and uses n words instead of 4n. Everything else: segment tree.

Lazy propagation is the extension that earns the tree its keep on range updates. “Add 5 to every element in [l, r)” costs O(n) on a prefix array and O(n log n) on a plain segment tree if you touch each leaf. With a lazy tag pushed down on demand, it is O(log n) — same as a point update. The cost is that your tag type has to compose with itself (applying “add 3” after “add 5” must collapse to “add 8”), and getting assignment-plus-addition tags to compose correctly is where most segment tree bugs live.

When the segment tree is the wrong answer

Reaching for one reflexively costs you code you have to maintain:

• n is small and queries are rare. A linear scan over 2,000 elements is a few microseconds. If you run a hundred queries total, the tree is pure overhead.
• Sums with point updates, nothing more. Use a Fenwick tree. Shorter, less memory, better cache behavior, far fewer places to get an off-by-one wrong.
• Range add plus range sum. Two Fenwick trees do this in less code than a lazy segment tree, if sums are all you need.
• Two dimensions. A tree of trees is O(n log^2 n) memory and miserable to debug. Check first whether the queries can be processed offline, sorted by one coordinate, and answered with a single 1D Fenwick tree sweeping across it.

One more practical note: the iterative bottom-up segment tree is short enough to type from memory once you have written it twice, and it avoids recursion overhead entirely. If you find yourself pasting a 120-line recursive template with lazy propagation into a problem that only needs range max on static data, you picked the wrong structure two steps earlier.