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."
Before you build anything, check whether your updates are actually interleaved with your queries. If the workload is "load the data, then answer a million range queries," you do not have a dynamic problem — you have a static one with a rebuild step. One O(n) prefix pass per batch beats every log-factor structure, and it is ten lines you will never have to debug at 2am.
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:
| Structure | Build | Query | Point update | Operation must be |
|---|---|---|---|---|
| Prefix sum array | O(n) | O(1) | O(n) | invertible (sum, xor) |
| Fenwick tree (BIT) | O(n) | O(log n) | O(log n) | invertible |
| Sparse table | O(n log n) | O(1) | full rebuild | idempotent (min, max, gcd) |
| Segment tree | O(n) | O(log n) | O(log n) | associative |
| Segment tree + lazy | O(n) | O(log n) | O(log n) per range | associative + composable tag |
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:
-
nis 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.
Size a recursive segment tree at
4 * n, not2 * n. The2 * nbound only holds for the iterative bottom-up layout on a power-of-two length. A recursive implementation indexing children as2*iand2*i+1can address past2 * nwhennis not a power of two, and the resulting out-of-bounds write is silent corruption rather than a crash. If the extra memory hurts, padnup to the next power of two and use2 * ndeliberately.
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.
Originally published at pickuma.com. Subscribe to the RSS or follow @pickuma.bsky.social for new reviews.
Top comments (0)