Euler Tour Trees

Store a tree’s Euler tour in a balanced BST, so that link and cut become sequence split and merge operations in $O(\log n)$.

The representation

The Euler tour of a tree with $n$ vertices is a sequence of $2n-1$ entries (each edge traversed twice, plus the vertices). Represent it as a balanced sequence — a treap or splay tree keyed implicitly by position.

Cut edge $(u,v)$ where $v$ is the child: the subtree of $v$ occupies a contiguous block of the tour. Split it out; that block is the new tree, and merging the two remaining pieces gives the old tree minus the subtree.

Link $u$ to $v$: re-root $v$‘s tour so $v$ is first (a cyclic rotation — two splits and a merge), then splice that tour into $u$‘s tour just after $u$‘s occurrence.

Both are $O(\log n)$: a constant number of splits and merges.

What it supports

Operation	Cost
link, cut	$O(\log n)$
connected(u, v)	$O(\log n)$ — same BST root
Subtree aggregate (sum, size, min)	$O(\log n)$
Subtree update	$O(\log n)$ with lazy tags
Point update	$O(\log n)$
Path aggregate	✘ not supported

Euler tour tree vs link-cut tree

	Euler tour tree	Link-cut tree
Subtree queries	✔	hard (needs virtual subtrees)
Path queries	✘	✔
Rooted-ness matters	no (unrooted)	yes (evert re-roots)
Implementation	moderate (sequence BST)	hard
Used inside	HDT dynamic connectivity	flow speedups, dynamic MST

They are complementary: paths versus subtrees. Neither subsumes the other.

Where they matter

Euler tour trees are the engine inside HDT dynamic connectivity: the algorithm maintains $O(\log n)$ nested spanning forests, each stored as Euler tour trees, and needs exactly the operations ETTs provide — link, cut, and “find any incident non-tree edge in this subtree”.

Outside that, they appear when a problem asks for subtree sums on a changing tree, which HLD and plain Euler tours cannot handle because the tour order itself changes.

In a contest

Almost never. If the tree is static, a plain Euler tour plus a BIT gives subtree queries in $O(\log n)$ with fifteen lines of code. If edges change and everything is offline, the segment-tree-on-time technique is simpler. Euler tour trees are for the genuinely online, genuinely dynamic case.

Implementation sketch

// treap over the Euler tour; each node carries a vertex id and an aggregate
Node* reroot(Node* t, int v) {
    Node *L, *R;
    split(t, posOf(v), L, R);       // rotate so v's first occurrence leads
    return merge(R, L);
}
void cut(int u, int v) {            // v is the child
    Node *A, *B, *C;
    split(root, tin[v], A, B);
    split(B, tout[v] - tin[v], B, C);
    root = merge(A, C);             // B is now v's subtree, a separate tree
}

Maintaining posOf under splits and merges requires storing parent pointers and walking up to compute a node’s index — an $O(\log n)$ operation in a treap.

See also: Euler Tour · Link-Cut Tree · Dynamic Connectivity