haccepted-0.1.0.0: Data structures and algorithms
Safe HaskellNone
LanguageHaskell2010

LCA

Description

Lowest common ancestor queries on a tree

Uses an Euler tour and a sparse table for range minimum queries, with an range size optimization from 2n to n, adapted from PyRival.

Sources:

Synopsis

Documentation

data LCA Source #

Instances

Instances details
Show LCA Source # 
Instance details

Defined in LCA

Methods

showsPrec :: Int -> LCA -> ShowS #

show :: LCA -> String #

showList :: [LCA] -> ShowS #

NFData LCA Source # 
Instance details

Defined in LCA

Methods

rnf :: LCA -> () #

buildLCA :: Bounds -> Tree Vertex -> LCA Source #

Build a structure for LCA queries on a tree. O(n log n).

queryLCA :: Vertex -> Vertex -> LCA -> Vertex Source #

Query the LCA of two nodes in a tree. O(1).

build1LCA :: Bounds -> [Tree Vertex] -> LCA Source #

Build a structure for LCA queries on a forest. O(n log n).

query1LCA :: Vertex -> Vertex -> LCA -> Maybe Vertex Source #

Query the LCA of two nodes in a forest. O(1).