Functions for finding lowest common ancestors in trees in O(1) time, with O(n) preprocessing.
Index is used as a node identifier, so that the user can refer to tree nodes
in a random-access fashion.
takes a tree whose nodes are mapped by
lowestCommonAncestor n ix tree
ix to a unique index in the range
0..n-1, and returns a function
which takes two indices (corresponding to two nodes in the tree) and returns
the label of their lowest common ancestor.
This takes O(n) preprocessing and answers queries in O(1), as it is an application of Data.RangeMin.
For binary trees, consider using Data.RangeMin.LCA.Binary.