rangemin-2.2.2: Linear range-min algorithms.



Functions for finding lowest common ancestors in trees in O(1) time, with O(n) preprocessing.



type Index = IntSource

The type of a vector index.

lowestCommonAncestor :: Int -> (a -> Index) -> Tree a -> Index -> Index -> aSource

lowestCommonAncestor n ix tree takes a tree whose nodes are mapped by 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.

quickLCA :: Tree a -> (Int, Tree (Index, a), Index -> Index -> (Index, a))Source

Takes a tree and indexes it in depth-first order, returning the number of nodes, the indexed tree, and the lowest common ancestor function.