Safe Haskell	None
Language	Haskell2010

HLD

Description

Heavy-light decomposition

Decomposition of a tree of size n into multiple paths, such that there are O(log n) paths between any pair of vertices.

HLD is useful for problems that have queries or updates on the path between two vertices.

This implementation maps each node to an integer position in [1..n] such that nodes in a path have consecutive positions. A path between two vertices decomposes into O(log n) ranges of consecutive integers, possibly simplifying the problem.

Sources:

Synopsis

data HLD = HLD {
- par_ :: !(UArray Vertex Vertex)
- dep_ :: !(UArray Vertex Int)
- hed_ :: !(UArray Vertex Vertex)
- pos_ :: !(UArray Vertex Int)
- siz_ :: !(UArray Vertex Int)
}
buildHLD :: Bounds -> Tree Vertex -> HLD
posHLD :: HLD -> Vertex -> Int
pathHLD :: HLD -> Vertex -> Vertex -> [(Int, Int)]
edgePathHLD :: HLD -> Vertex -> Vertex -> [(Int, Int)]
subtreeHLD :: HLD -> Vertex -> (Int, Int)
lcaHLD :: HLD -> Vertex -> Vertex -> Vertex

Documentation

data HLD Source #

Constructors

HLD
Fields par_ :: !(UArray Vertex Vertex) dep_ :: !(UArray Vertex Int) hed_ :: !(UArray Vertex Vertex) pos_ :: !(UArray Vertex Int) siz_ :: !(UArray Vertex Int)

Instances

Instances details

NFData HLD Source #
Instance details Defined in HLD Methods rnf :: HLD -> () #

buildHLD :: Bounds -> Tree Vertex -> HLD Source #

Builds the HLD structure from a tree. O(n).

posHLD :: HLD -> Vertex -> Int Source #

The position for the given vertex. O(1).

pathHLD :: HLD -> Vertex -> Vertex -> [(Int, Int)] Source #

A list of position ranges which make up the path from u to v. O(log n).

edgePathHLD :: HLD -> Vertex -> Vertex -> [(Int, Int)] Source #

pathsHLD but excludes the LCA. Useful when working with edges, each edge can be mapped to the node it leads down into. O(log n).

subtreeHLD :: HLD -> Vertex -> (Int, Int) Source #

A position range covering the subtree of the given node. O(1).

lcaHLD :: HLD -> Vertex -> Vertex -> Vertex Source #

The lowest common ancestor of two vertices. O(log n).