This site's Array-Backed Trees category holds fifteen
entries, but only six answer the same underlying question: given an array, keep some running
answer over ranges of it fast, even as the array changes. Segment Tree, Fenwick Tree, Sparse Table, Segment Tree with Lazy Propagation, Persistent Segment Tree, and Sqrt Decomposition all trade a build cost up
front for fast point-query-or-update over ranges of the same underlying array. The other nine
entries each answer a genuinely different question, for different reasons, so all nine sit outside
the comparison below — the same way the Minimum Spanning Tree guide
sets aside two of its six entries before comparing the ones that build the same tree. Binary Heap repeatedly pulls the current minimum (or maximum)
out of a changing set, not a query over an arbitrary range, and Min-Max Heap extends that same pulled-extreme
question to both ends at once — still not a range query over array positions either way. Mo's Algorithm does query arbitrary ranges, but only for a
fixed batch of queries known entirely in advance, answered by reordering them rather than
maintaining a persistent structure at all — see its own page for when that offline trade is worth
making over everything below. Van Emde Boas
Tree doesn't touch ranges at all — it answers membership and successor/predecessor for a single
value, over a fixed bounded universe, at a complexity measured against the universe size rather
than against how many elements are actually stored.
X-Fast Trie answers that same membership/successor/predecessor question, over the same kind of
fixed universe, so it sits outside the comparison for the identical reason — a different mechanism
(a hash table per bit-level plus a binary search, instead of vEB's recursive clusters) for the
exact same different question, not a second question of its own. Wavelet Tree and Merge Sort Tree both answer questions about
values within a range, not a single running combined answer over one — which symbol, how many
values are at most x, which occurrence — the former with a complexity model built
around the alphabet size, the latter with plain sorted arrays and binary search at the cost of more
space, two different mechanisms for the same different question rather than two questions of their
own. Fractional Cascading isn't about one
changing array at all — it speeds up the same query repeated across several separate, unchanging
catalogs, which none of the six below even attempt. Li
Chao Tree doesn't hold array values at all — it answers which of several inserted
lines is largest at a query x, the same question Convex Hull Trick answers under a stricter ordering
requirement, with no array or range-combining operation anywhere in sight.
Do you need to ask what a range looked like at some earlier point, after updates have
already happened since? Only one entry keeps every past version queryable at all — if the
answer is yes, nothing else below matters. If not, does the array ever change once
built? Never changing opens up the one case where a query can be genuinely
O(1), but only for a specific kind of operation. If it does change, does an
update ever need to touch a whole range at once, not just one element? If updates
are point-only, does the combining operation have an inverse — like sum, where subtraction undoes
addition — or not, like minimum? That question decides the least on its own among the
first four, which is why it comes last among them: it only matters once history, frozen-ness, and
range-vs-point updates have already ruled out the structures that don't apply. Last,
regardless of how that fourth question lands: is O(log n) actually required, or would
a worse-but-simpler O(√n), no-tree-at-all structure do? That fifth question
is the odd one out — it doesn't rule anything in or out by problem shape the way the first four do,
it's a genuine style tradeoff available at every point on the funnel above it.
Persistent Segment Tree is the only
entry on this page where every version that has ever existed stays queryable forever. The
mechanism is structural sharing: an update allocates only the O(log n) nodes on the
path from root to the changed leaf, and every other node — the vast majority of the tree — is the
literal same object the old version already pointed to. Its own page measured this directly: the
demo's 8-leaf tree costs 15 nodes for the first version, then exactly 4 more per update, for
O(n + m log n) nodes total after m updates — not the full O(n)
copy-the-whole-array-every-time a naive "just keep old snapshots" approach would cost. This site's
own demo builds it specifically for range sum with point updates — the same territory Fenwick Tree covers below, plus full history layered
on top — not for range updates or non-invertible operations, so treat persistence as a need that
gets bolted onto the same point-update-plus-sum case, not a free upgrade available to any of the
other four. It's also only partial persistence, the same boundary Persistent
Union-Find draws around itself: every past version stays queryable, but a new update always
extends the current latest version — there's no branching a second future off some older version
without touching everything built on top of it since.
If the array is frozen for good once built, Sparse
Table gets the query down to O(1) — no tree walk, no loop, one lookup combining
two precomputed ranges that are allowed to overlap in the middle. That overlap is the entire
trick, and it only works when the combining operation doesn't care about being asked about the
same elements twice. Its own page
verified this exhaustively, not just asserted it: the same two-block query logic that matches a
naive scan on all 36 possible ranges of an 8-element array in min mode is wrong on
all 36 of those same ranges in sum mode — even a range whose length is already a
power of two ends up counting the identical cell twice, silently doubling the true answer. Min,
max, and gcd are idempotent and safe; sum, count, and product are not and need Fenwick Tree or Segment Tree instead, never a sparse table. One
honest exception this guide's own tree doesn't cover: if the array is frozen and the
operation is sum, none of this category's five entries is even the right tool — a plain
precomputed prefix-sum array already answers any range sum in O(1) with a single
O(n) build pass, cheaper on both axes than sparse table's O(n log n)
build and O(n log n) space.
Once the array does change, the next fork is what an update looks like. A plain segment tree's update only ever
touches one index — adding 10 to every element in a five-element range means five separate
root-to-leaf walks, O(k log n) for a k-element range. Segment Tree with Lazy Propagation gets a
whole-range update back down to O(log n): when an update's target range exactly
covers a node's own range, it stops there and parks the pending change as a tag on that one node,
pushing it down into the children only later, if and when some other operation actually needs to
see inside. The cost is a second array the same size as the tree, tracking one pending value per
node where the plain segment tree tracks none — real, but a flat constant-factor tax next to the
asymptotic win on range updates. If every update in your workload only ever touches a single
element, that tax buys nothing; reach for the plain segment tree or Fenwick tree instead, covered
next.
With range updates and history off the table, the deciding question is whether the combining
operation has an inverse. Sum does — rangeSum(l, r) = query(r) - query(l-1), since
subtraction undoes addition — and that's exactly what Fenwick Tree is built for: both point update and
prefix query in O(log n), using one flat array of size n+1 and no
per-node overhead at all. Segment tree's own
page is explicit about the tradeoff from the other side: for a genuinely invertible operation
like sum, a Fenwick tree is simpler code and about half the memory (one array of size
n+1, versus a segment tree's own array running up to 4n once it's padded
to the next power of two). Minimum, maximum, and gcd have no such inverse — knowing the smallest
value up to index r and the smallest value up to index l-1 says nothing
about which side the true minimum of [l, r] came from — so those need a plain segment tree instead, which asks for less (any
associative combining rule, not an invertible one) and in exchange supports arbitrary range
queries at roughly double the memory and a small constant-factor slowdown versus Fenwick's tighter
array.
Every structure above answers in O(log n) by building an actual tree — recursive or
iterative, node objects or a flat array doubled up to the next power of two. Sqrt Decomposition answers the same
point-update-plus-range-query question Segment Tree does (any associative operation, no
inverse required) with no tree at all: chop the array into blocks of about √n
elements, precompute each block's own answer, and a query scans at most two partial blocks by hand
plus reads a run of whole blocks straight from the precomputed table. The cost is real —
O(√n) is asymptotically worse than O(log n), and the gap widens with
n — but its own page
verified something the other five don't share: the update cost genuinely depends on which
operation you picked, not just a fixed O(log n) regardless. Sum can apply a delta to
a block's running total in true O(1), the same invertibility trick that makes Fenwick
tree work; minimum and maximum have no such shortcut and must rescan the whole touched block,
O(√n). Reach for this over segment tree specifically when the flat-array simplicity
(no recursion, no power-of-two padding) is worth more than the asymptotic gap — or as the base to
extend with a per-block operation more elaborate than a running minimum, which the tree-shaped
structures above don't offer as naturally.
| Entry | Update | Query | Space | Reach for it when |
|---|---|---|---|---|
| Persistent Segment Tree | O(log n), point, adds a new version | O(log n), any past version | O(n + m log n) after m updates | need to query how a range looked before later updates happened |
| Sparse Table | none — array is frozen | O(1) | O(n log n) | array never changes, operation is idempotent (min, max, gcd) |
| Segment Tree with Lazy Propagation | O(log n), whole range at once | O(log n) | O(n), doubled over plain segment tree | updates apply to whole ranges, not single elements |
| Fenwick Tree | O(log n), point only | O(log n) | O(n) | point updates, operation is invertible (sum) |
| Segment Tree | O(log n), point only | O(log n) | up to O(4n) | point updates, operation has no inverse (min, max, gcd) |
| Sqrt Decomposition | O(√n) always; O(1) if the operation is invertible | O(√n) | O(n) | flat-array simplicity over the O(log n) any of the tree-shaped entries above give you |