Functions for finding lowest common ancestors in trees in O(1) time, with O(n) preprocessing.
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.