Online LCA, in depth: streaming queries, growing trees, jump pointers with O(1) insertion and when to use a sparse table

Two meanings of online

Online queries, static tree. The tree is known, and queries arrive one at a time, for example from an API, or in a forced-online problem where each query is decoded with the previous answer (u = u_raw ^ last). You may preprocess the tree as much as you like.

Online queries, growing tree. Nodes arrive as new leaves interleaved with queries: a version tree that gains commits, a search tree that expands during MCTS, a comment thread that gains replies, a phylogeny that gains samples. Any structure that needs a full rebuild after an insert is ruled out. The question becomes how cheaply a leaf can be attached.

A third case, where edges are cut and re-linked, needs dynamic trees. That is covered in link-cut trees in depth.

Baseline: binary lifting

The default answer for both cases is binary lifting. Store up[k][v], the 2^k-th ancestor of v, for k up to log₂ n. To answer a query, lift the deeper node to the other's depth with the binary digits of the difference, then lift both together from the highest k down while their ancestors differ. The parent of where they stop is the LCA.

def add_leaf(v, p):                    # works online: ancestors already exist
    depth[v] = depth[p] + 1
    up[0][v] = p
    for k in range(1, LOG):
        up[k][v] = up[k - 1][up[k - 1][v]]

def lca(u, v):
    if depth[u] < depth[v]: u, v = v, u
    diff = depth[u] - depth[v]
    for k in range(LOG):
        if diff >> k & 1: u = up[k][u]
    if u == v: return u
    for k in reversed(range(LOG)):
        if up[k][u] != up[k][v]: u, v = up[k][u], up[k][v]
    return up[0][u]

Adding a leaf costs O(log n) and a query costs O(log n), but memory is LOG integers per node: 17 per node at n = 100,000, and the table has to be sized for the final n. Rooting, ancestor tests and path aggregates built on this are covered in the LCA deep dive.

Static trees: Euler tour and a sparse table

When the tree is fixed and queries are numerous, reduce LCA to range minimum. Record the 2n - 1 node Euler tour of a DFS, each node's first position, and depths. Then lca(u, v) is the shallowest node in the tour between first[u] and first[v]. A sparse table over the tour answers that in O(1) with two overlapping power-of-two windows, after O(n log n) preprocessing. The construction and proof are in Euler tour on tree.

One correction to a claim that circulates: the plain sparse table does not use the ±1 property. It works for any array. The fact that adjacent tour depths differ by exactly one is what the Farach-Colton and Bender method exploits to get O(n) preprocessing. It cuts the tour into blocks of about (log n)/2, precomputes every possible block shape, and builds a sparse table only over block minima. It is rarely worth the complexity in practice. The same reduction run backwards, RMQ to LCA, is how Cartesian trees answer range minimum.

None of this survives growth. A new leaf inserts two entries in the middle of the tour and shifts every later index, so the sparse table must be rebuilt.

Growing trees: jump pointers

There is a structure with O(1) memory per node, O(1) leaf insertion and O(log n) queries. Each node stores its parent, its depth and a single jump pointer. A new leaf v under p sets its jump by one rule:

• Let j = jump[p]. If the gap from p to j equals the gap from j to jump[j], that is, depth[p] - depth[j] == depth[j] - depth[jump[j]], then jump[v] = jump[j].
• Otherwise jump[v] = p.

Two equal-length jumps merge into one that is twice as long plus one step. The resulting jump lengths follow the skew-binary number system (1, 3, 7, 15, and so on), and that is what bounds every walk by O(log n) jumps. Crucially, a node's jump target depth depends only on its depth. Two nodes at the same depth always jump to the same depth. That is what makes the LCA walk work:

class GrowingTree:
    # Online LCA on a tree that grows by leaves: O(1) add, O(log n) query.
    def __init__(self):
        self.parent = [0]; self.jump = [0]; self.depth = [0]   # node 0 is the root
    def add_leaf(self, p):
        v = len(self.parent)
        j = self.jump[p]
        if self.depth[p] - self.depth[j] == self.depth[j] - self.depth[self.jump[j]]:
            jv = self.jump[j]
        else:
            jv = p
        self.parent.append(p); self.jump.append(jv); self.depth.append(self.depth[p] + 1)
        return v
    def lift(self, v, d):                      # ancestor of v at depth d
        while self.depth[v] > d:
            v = self.jump[v] if self.depth[self.jump[v]] >= d else self.parent[v]
        return v
    def lca(self, u, v):
        if self.depth[u] < self.depth[v]: u, v = v, u
        u = self.lift(u, self.depth[v])
        while u != v:                          # same depth, so jumps land on the same depth
            if self.jump[u] != self.jump[v]:
                u, v = self.jump[u], self.jump[v]
            else:
                u, v = self.parent[u], self.parent[v]
        return u

The final loop is a search over a monotone predicate. If the jump targets differ, the LCA is above them, so take the jump on both sides. If they are equal, the LCA is at or below them, so step one parent and try again with shorter jumps. This was tested against a naive parent-walking LCA and against an Euler-tour sparse table on 200 random trees (random, path and broom shapes, up to 300 nodes), 200 queries each, with no mismatches.

Worked example

Build the tree in the figure by adding leaves under parents 0, 0, 1, 1, 2, 4, 4, 6, which creates nodes 1 to 8. Nodes 6 and 7 sit at depth 3, under node 4 whose jump goes to 1 and whose jump-of-jump goes to 0. The gaps are equal (1 and 1), so jump[6] = jump[7] = jump[1] = 0. Node 8 at depth 4 sees parent 6 with gap 3 to node 0 and a gap of 0 beyond it, so it falls back to jump[8] = 6.

• lca(8, 3). Lift 8 to depth 2: jump[8] = 6 (depth 3, at least 2) so take it, then jump[6] = 0 overshoots, so step to parent 4. Now compare 4 and 3. Their jumps are both 1, so step to the parents, 1 and 1. The answer is 1.
• lca(7, 5). Lift 7 to depth 2: jump[7] = 0 overshoots, so take parent 4. Compare 4 and 5. Their jumps are 1 and 2, which differ, so jump both. Now compare 1 and 2. Their jumps are both 0, so step to the parents, 0 and 0. The answer is 0.

Measured cost

Asymptotics hide constants, so the steps were measured: the total of lift plus loop iterations per query, worst case over 20,000 random queries on 100,000-node trees.

Jump pointers take about twice the steps of binary lifting on deep adversarial trees, with 3 integers per node instead of 18 and constant-time insertion with no preallocated table. On shallow trees such as the random one above, they do fewer steps than lifting.

Choosing a structure

Failure modes

• Recursion depth. A recursive DFS for the Euler tour overflows on a 100,000-node path in Python and on deeper trees in C++. Use an explicit stack.
• Root jump. The root must point to itself (jump[0] = parent[0] = 0). Otherwise the gap rule reads garbage on the first insertions.
• Forests. Join multiple roots under a virtual root and treat an answer equal to that root as "not connected".
• Forced-online decoding. Decode with the previous answer as the problem defines it. Off-by-one decoding produces plausible but wrong answers that only stress tests catch.
• Sparse table size. The table is built over 2n - 1 entries, not n. Size LOG for the tour length.

The jump-pointer rule is short enough to get subtly wrong, for example by comparing the gap of the wrong pair of nodes. A wrong rule still returns an ancestor and usually the right one. Keep a randomised stress test next to the implementation and run it in CI:

import random

def naive(par, dep, u, v):
    while dep[u] > dep[v]: u = par[u]
    while dep[v] > dep[u]: v = par[v]
    while u != v: u, v = par[u], par[v]
    return u

for trial in range(200):
    t, n = GrowingTree(), random.randint(1, 300)
    for v in range(1, n):
        t.add_leaf(random.choice([v - 1, random.randrange(v)]))   # mix paths and bushes
        a, b = random.randrange(v + 1), random.randrange(v + 1)   # query while growing
        assert t.lca(a, b) == naive(t.parent, t.depth, a, b)

Querying between insertions matters: it is the online case, and it catches bugs that only appear while the jump structure is half-built.

Trade-offs

The O(1)-query structure is the fastest per query, but it is also the largest and it cannot absorb an insert. Binary lifting is the simplest general tool but costs a log factor of memory. Jump pointers are the leanest and the only one with constant-time leaf insertion, at the cost of an unfamiliar invariant that deserves a stress test in your code base. In a service, a cache miss per pointer chase often matters more than the step count, so benchmark with your tree shapes.

What to do next

1. Decide which online you have: static tree with streaming queries, a growing tree, or a fully dynamic one.
2. Write a naive parent-walking LCA first. It is the oracle for every test you write.
3. Implement GrowingTree above and stress-test it against the oracle on paths, brooms and random trees.
4. If the tree is static and queries dominate, add Euler tour + sparse table and compare time and memory.
5. Measure worst-case steps on your real tree shapes, not just random ones.
6. Build distance and path queries on top: dist(u, v) = depth(u) + depth(v) - 2 depth(lca).