Non-Recursive HLD Implementation

Revision en2, by mango_lassi, 2019-05-22 07:59:19

I wrote this pretty short implementation of Heavy-Light Decomposition today:


It uses no recursion, which is nice, and takes data in the index-of-parent format, which can be a small plus or a large minus (I needed HLD over Aho-Corasick automata, so that input format is useful there). The intervals returned by get are in decreasing order, not in the order they are in the path, so something like adding an arithmetic sequence to a path is not possible.

The par-array just stores the parent of every node, ind gives the index of the node in the array HLD maps the nodes to, and pp gives the highest ancestor of the node that is mapped to the same continuous segment.

get returns a vector of at most $$$O(log(n))$$$ intervals, such that hld-index of every node on the path between $$$a$$$ and $$$b$$$ is in exactly one of the returned intervals. Specifically it returns all intersections of heavy paths with the path between $$$a$$$ and $$$b$$$ that are nonempty, in decreasing order (first interval has highest startpoint and endpoint). Clearly there are at most $O(log(n))$ such intervals, since every path contains at most $O(log(n))$ light edges, so at most $O(log(n))$ heavy intervals.

Get works since the path from $$$b$$$ to $$$pp[b]$$$ corresponds to the continuous interval $$$ind[pp[b]], ind[b]$$$ in the array HLD maps the nodes to, and therefore if $$$ind[pp[b]] \leq ind[a] \leq ind[b]$$$, $$$a$$$ is on the path between $$$pp[b]$$$ and $$$b$$$, and if $$$ind[a] < ind[pp[b]]$$$, then no node we go over is an ancestor of $$$a$$$, since the HLD-index of a node's ancestor is always less than the ind of the node.

Since get also finds the LCA, this also gives a nice LCA implementation:


Here's Caves and Tunnels solved with this HLD-implementation. Changing the tree format is pretty nasty, so the code isn't that clean :/

Tags hld, implementation, lca, datastructure


  Rev. Lang. By When Δ Comment
en2 English mango_lassi 2019-05-22 07:59:19 7 Tiny change: '\n ind[i] = cur;\n' -> '\n ind[j] = cur;\n'I had fixed a bug in the Caves and Tunnels version of HLD that still existed in the first code.
en1 English mango_lassi 2019-05-21 19:50:30 6388 Initial revision (published)