Proofs: Euler tour tree

The operations of an Euler tour tree keep the Euler tour invariant full

This proof shows: correctness.

We use the invariant (E) of the page. For a tree $T$, an Euler sequence of $T$ is a cyclic sequence of loop nodes and arc nodes with the three properties of (E). We first prove two facts about Euler sequences, then show that each operation maps Euler sequences of the old forest to Euler sequences of the new forest, and that each query reads the right value.

Lemma 1 (ends of a rotation). Let $S$ be an Euler sequence of a tree $T$ with at least two vertices, rotated so that it starts with the loop node $(w, w)$. Then the first arc of $S$ leaves $w$ and the last node of $S$ is an arc into $w$.

Proof. By (E3), the loop node $(w, w)$ lies cyclically between an arc into $w$ and an arc out of $w$. In the rotation that starts with $(w, w)$, the node cyclically before it is the last node of $S$, and the next arc after it is the first arc of $S$. A loop node is never between two arcs of different vertices, so the node before $(w,w)$ is an arc into $w$ (and not another loop node, since by (E3) each loop node sits between arcs and $T$ has an arc at $w$). $\square$

Lemma 2 (the two arcs of an edge). Let $S$ be an Euler sequence of a tree $T$, let $\{u, v\}$ be an edge of $T$, and let $T_u$ and $T_v$ be the two trees of $T$ without this edge, with $u \in T_u$ and $v \in T_v$. Write $S = X\,a\,Y\,b\,Z$, where $\{a, b\} = \{(u, v), (v, u)\}$ and $a$ comes first. Let $w$ be the head of $a$. Then $Y$ is an Euler sequence of the side $T_w \in \{T_u, T_v\}$ that contains $w$, and the cyclic sequence $Z\,X$ (equal, as a cyclic sequence, to $X$ followed by $Z$ in the treap order) is an Euler sequence of the other side.

Proof. Every arc of $T$ other than $a$ and $b$ has both ends in $T_u$ or both ends in $T_v$, because $\{u, v\}$ is the only edge between the two sides. The walk of (E1) is at $w$ just after $a$. Each later arc of $Y$ starts where the previous one ends, and none of them is $a$ or $b$, so by induction along $Y$ every arc of $Y$ has both ends in $T_w$. The arc $b$ leaves the tail of $a$'s head, that is, $b$ starts at $w$; so the last arc of $Y$ ends at $w$ (or $Y$ has no arc). Hence the arcs of $Y$ form a closed walk at $w$ inside $T_w$. In the same way, the arcs of $Z\,X$ form a closed walk inside the other side, since they start after $b$ at the head of $b$ and end before $a$ at the tail of $a$, which is the same vertex. Each arc of $T_w$ occurs once in $S$ by (E2), and it is not in $Z\,X$, so it is in $Y$; the same holds for the other side. So (E1) and (E2) hold for both parts.

For (E3), take a loop node $(x, x)$. If $T$ has at least two vertices, by (E3) for $S$ it lies between an arc into $x$ and an arc out of $x$. If neither neighbor arc is $a$ or $b$, both are in the same part as $(x, x)$, and $x$ is in the side of those arcs. If the arc before $(x, x)$ is $a$, then $x = w$ and $(x, x)$ is in $Y$; if the arc after it is $b$, then $x = w$ again, since $b$ starts at $w$, and $(x, x)$ is in $Y$. If the arc after $(x,x)$ is $a$, then $x$ is the tail of $a$, which is in the other side, and $(x, x)$ is at the end of $X$; if the arc before it is $b$, then $x$ is the head of $b$, in the other side, and $(x, x)$ is at the start of $Z$. So each part holds exactly the loop nodes of its side. A loop node next to $a$ or $b$ now has, in its part, the neighbor arcs that the closed walk of its part gives it, and if its side is a single vertex, the part is that loop node alone. $\square$

Theorem. After each operation, the treaps of the structure hold one Euler sequence for each tree of the current forest, and each query returns the value of its definition.

Proof. By induction on the number of operations. At the start the forest has no edges, and each vertex $v$ has the sequence $(v, v)$, which satisfies (E). Assume that (E) holds before an operation.

Reroot (lines L1 and L2) replaces $S = A\,B$ by $B\,A$, which is the same cyclic sequence, so (E) still holds.

Link$(u, v)$ (lines L4 to L6), where $u$ and $v$ are in different trees $T_1$ and $T_2$. After line L4, $S_u$ starts with $(u, u)$ and $S_v$ with $(v, v)$. Consider $S = S_u\,(u, v)\,S_v\,(v, u)$. If $T_1$ has an edge, by Lemma 1 $S_u$ ends with an arc into $u$, so the next arc $(u, v)$ continues the walk; if $T_1$ is the single vertex $u$, $S_u$ has no arc and the arc before $(u, v)$ cyclically is $(v, u)$, which ends at $u$. The same argument at $v$ shows that $(u, v)$ is followed by the walk of $S_v$ from $v$ back to $v$, and then by $(v, u)$, which returns to $u$, where the walk of $S_u$ starts. So the arcs of $S$ form a closed walk (E1). It uses each arc of $T_1$ and $T_2$ once and the two new arcs once (E2). Each old loop node keeps its old neighbors except that $(u, u)$ now has $(v, u)$ before it and the first arc of $S_u$ (or $(u, v)$) after it, and $(v, v)$ has $(u, v)$ before it and the first arc of $S_v$ (or $(v, u)$) after it, all with the right ends (E3).

Cut$(u, v)$ (lines L7 to L10). Line L8 orders the two arcs by position, and line L9 writes the sequence as $X\,a\,Y\,b\,Z$ in treap order. A cyclic Euler sequence read from position 0 is also read cyclically, so Lemma 2 applies: $Y$ is an Euler sequence of one side and $X$ followed by $Z$ is one of the other. Line L10 stores these two sequences, and the two arc nodes are deleted.

Set value changes one loop value and recomputes the sums on the path to the treap root, so every stored sum is again the sum of its subtree.

Queries. By (E3), the loop nodes of a sequence are exactly the vertices of its tree, so line L3 answers connectivity, and the loop count and sum at the treap root (line L11) are the size and the value sum of the tree. For $\mathrm{subtree\_sum}(v, p)$, apply Lemma 2 to the rotation of the sequence that starts at position 0, with $a$ the first of $(p, v)$ and $(v, p)$. If $(p, v)$ comes first ($i < j$), then $w = v$, and the side of $v$ is the segment strictly between positions $i$ and $j$ (line L13). If $(v, p)$ comes first ($j < i$), then $w = p$, the segment strictly between $j$ and $i$ is the side of $p$, and the side of $v$ is the rest; since arc nodes have value 0, its sum is the total minus the sum of positions $j + 1$ to $i - 1$ (line L14). $\blacksquare$