An algorithm is online if it has to produce a correct answer to each request the instant it arrives, with no visibility into what comes after. It's offline if it's allowed to see every request first, then answer them in whatever order actually helps — not necessarily the order they were asked in. The underlying question doesn't have to change at all for this to matter: three pairs of entries on this site answer the exact same question both ways, and each source page already names its own online or offline counterpart on its own terms. This page is the first time all three sit side by side, because the shape of the payoff turns out to be different in each one — not one simple rule repeated three times.
Offline Lowest Common
Ancestor (Tarjan's Algorithm) needs the whole batch of (u, v) query pairs fixed
before it starts — its own opening line calls that "the load-bearing word," because the trick is
letting a single depth-first walk decide when each query becomes answerable, rather than answering
on demand. Its own Complexity section states the cost plainly:
O((n + q)·α(n))
time, O(n) space — one DFS pass, no per-query tree walk, the near-constant
inverse-Ackermann bound Union-Find's own page already established.
Binary Lifting drops the whole-batch
requirement entirely — its own opening line names Offline LCA directly: that page "names this one as
'future work' for the case Tarjan's algorithm can't handle." Build a jump table once in
O(n log n) time and
space, then answer LCA(u, v) for any pair, in any order, interleaved with
anything else, at any time afterward — each query costs O(log n). Its own Complexity
section names the exact price of that freedom: O(n log n) space against Offline LCA's
O(n), "the price of answering queries in any order instead of just the ones known in
advance."
This is the cleanest of the three pairs because offline wins on every axis — total time and space — whenever the batch really is known up front. The only reason to pay binary lifting's steeper build cost is not having that batch, or needing to answer a query whose own nodes depend on an earlier query's result.
Mo's Algorithm answers a fixed batch of range
queries over an array that never changes — its own opening line draws the contrast directly:
"every other entry in this category answers range queries online — one query arrives, you
answer it immediately, then the next one arrives. Mo's Algorithm is for a different shape of
problem." Reorder the whole batch by √n-sized block, and a single sliding window
answers all of them for a total cost of
O((n + m)·√n) — amortized across
the batch, not a per-query bound.
Here the payoff isn't raw speed — a segment
tree or Fenwick tree answers any single online
query in a strict O(log n), asymptotically tighter than Mo's O(√n)
amortized share per query. What offline unlocks instead is a whole class of queries that have
no efficient merge step at all: Mo's own page names the example directly — "how many
distinct values appear in [L, R]" has no efficient merge, because "knowing the
distinct count of the left half and the right half separately doesn't tell you how many values they
share," but it has a trivial single-element update. A segment tree literally cannot answer that
query, mergeable or not — it isn't a speed gap to close, it's a different tool for a question the
online structures can't address at all.
Offline Dynamic Connectivity
needs every edge's full [start, end) lifetime known before it starts, decomposed onto
a segment tree built over time itself rather than over array indices. Knowing the whole timeline up
front is what lets a comparatively simple structure — Union-Find with Rollback, undoing unions as a
DFS over that time-segment-tree backs out of each node — answer "are these two nodes connected
right now?" at any past moment, in
O((n + m·log T)·log
n) total.
Link-Cut Tree is the fully online version of
the identical question — edges linked and cut in any order, arriving forever, with no
whole-timeline-up-front requirement at all. Its own Complexity section names real uses that "lean on
exactly this online generality: maintaining minimum spanning trees under edge insertions and
deletions... a setting where Offline Dynamic Connectivity's whole-timeline-up-front requirement
doesn't fit, because the next edit depends on an answer that hasn't been computed yet." The price is
a genuinely heavier structure — splay trees linked by preferred-path pointers, amortized
O(log n) per operation, measured directly on this site at 1.16×–1.33× log₂
n rotations per access across three tree sizes — in exchange for never needing to know the
future at all.
The LCA pair above gives two formulas for the same job, both already proved on their own pages:
offline total cost ≈ (n + q)·α(n), with α(n) "under 5 for any input you could ever
construct in practice" per Union-Find's own
Complexity section — call it 4; online total cost (one-time build plus every query) ≈
(n + q)·log₂(n). Both scale identically in (n + q), so their
ratio depends on n alone, never on how many queries you ask — a fact that
falls straight out of the two formulas, not a separate claim to verify. Drag the slider to pick a
tree size and watch the gap that leaves.
The batch has to be genuinely known, not just known soon. If even one query's identity depends on a result that hasn't been computed yet — an LCA query whose two nodes are chosen based on an earlier query's answer, a range query triggered by what a previous one returned — the whole-batch trick breaks before it starts, because each offline structure above needs the complete set to decide its own processing order. Mo's own Pitfalls section states the general version directly: "the whole batch of queries has to be known before you start... unusable the moment a query needs an answer before the rest of the batch is even known."
"Offline" doesn't mean "any order" — it means the one specific order the algorithm's
proof actually depends on. Tarjan's offline LCA needs DFS finish order; Mo's Algorithm needs
the specific block-sort by L, then R; Offline Dynamic Connectivity needs the
edge-lifetime decomposition over a segment tree built on time. None of these save work through
"process it in a convenient order" in general — they save work through one precise reordering each
proof is built around.
Assuming the reordering is a performance nicety, not the entire argument. Mo's
Algorithm's own page measured this directly, not just asserted it: skipping the block-sort and
processing the identical queries in arrival order cost 13.3× more pointer moves on a
1,000-element array, and 18.9× more on a 2,000-element one — the same answers,
dramatically more work, because the sort is what the O(√n) bound is actually about, not
a tidiness pass on top of it.
Assuming offline is strictly faster because it was in the LCA pair. The range-query
pair above is the counterexample sitting right next to it: a segment tree's online O(log
n) per query is asymptotically tighter than Mo's offline O(√n) amortized share.
Offline's real payoff there is answering a question (distinct count) online structures can't answer
at all, not raw speed — don't generalize "offline wins" from one pair to all three.
Treating "online" as just "offline without the batch," rather than a genuinely harder problem needing different machinery. Link-Cut Tree's splay-tree-backed structure is not a small tweak to Union-Find with Rollback's DFS-and-undo — it's a different data structure entirely, because the online version has to stay correct under an edge order that isn't known yet, a guarantee the offline version is never asked to provide.