# What is the fastest deterministic algorithm for incremental dynamic tree reachability?

As the title. The dynamic algorithm maintains the transitive closure of a tree when the tree undergoes a series of edge insertions (but no deletions)? And the algorithm supports constant query time.

The paper (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) introduces an algorithm for maintaining the transitive closure of a graph with O(n) amortized time pre insertion. I wonder whether better algorithm exists for trees?

• Do you want constant query time? – George Apr 12 '13 at 13:39
• Yes, constant query time. I have updated the question. – wei wang Apr 13 '13 at 11:39
• Directed or undirected trees? – David Eppstein Apr 13 '13 at 15:10
• Also, what do you mean by a tree undergoing edge insertions? Unless the vertex set changes, the number of edges in a tree cannot change. Do you mean that you have a forest on a fixed vertex set? Or do you mean that you have a tree, and can insert a new leaf vertex? – David Eppstein Apr 14 '13 at 0:09
• It should be "a forest on a fixed vertex set" and directed trees. – wei wang Apr 14 '13 at 8:42

The best I can find for this is $O(\log n)$ amortized update time with constant query time. The basic idea is that if you know both preorder and postorder for a tree, you can recover reachability: there is a path from $x$ to $y$ iff $x$ is before $y$ in preorder and after it in postorder.
To add an edge from a node $x$ to a node $y$ (where prior to the addition, $y$ is the root of a tree) we need to merge the orderings for two trees. Do so by finding which of the two trees is smaller, adding its vertices into the ordering structures for the tree that is larger, and changing the node labels on the nodes in the smaller tree to point to the larger one. In this way, each vertex participates in $O(\log n)$ updates over the lifetime of the structure (every time it is part of the smaller tree, the size of the tree it is in doubles). More precisely, each tree with $k$ edges takes total time $O(k\log k)$ to build, so the amortized time per edge is logarithmic.