Safe Haskell	None
Language	GHC2021

AtCoder.Extra.Tree.Lct

Contents

Constructors
Monoid value access
Tree operations
- Link/cut
- Evert/expose
Tree queries
- Monoid products

Description

Link/cut tree: dynamic forest with monoid values on vertices. If you need to have monoid values on edges, treat the original edges as new vertices.

Most operations are unsafe; user must ensure connectivities of $u$ and $v$ before running each query.
This specific implementation is not capable of applying monoid action to a subtree.

Example

Expand

Create a link/cut tree of monoid Sum Int with inverse operator negate:

>>> import AtCoder.Extra.Tree.Lct qualified as Lct
>>> import Data.Semigroup (Sum (..))
>>> import Data.Vector.Unboxed qualified as VU
>>> -- 0--1--2
>>> --    +--3
>>> lct <- Lct.buildInv negate (VU.generate 4 Sum) $ VU.fromList [(0, 1), (1, 2), (1, 3)]

`prodPath`, `prodSubtree`, `prodTree`

Monoid products can be calculated for paths or subtrees:

>>> Lct.prodPath lct 0 2
Sum {getSum = 3}

>>> -- If we create the LCT with `buildInv`, we can use `prodSubtree`:
>>> Lct.prodSubtree lct 1 {- parent -} 2
Sum {getSum = 4}

root returns the current root vertex of the underlying tree, which is not easy to predict:

>>> Lct.root lct 3
2

`lca`, `jump`, `lengthBetween`

Set (evert) the root of the underlying tree to $0$ and get the lca of vertices $2$ and $3$ :

>>> Lct.evert lct 0
>>> Lct.lca lct 2 3
1

Similar to Hld, Lct allows various tree queries:

>>> Lct.jump lct {- path -} 2 3 {- k -} 2
3

>>> Lct.jumpMaybe lct {- path -} 2 3 {- k -} 1000
Nothing

>>> Lct.lengthBetween lct {- path -} 2 3
2

`parent`

>>> Lct.evert lct 0  -- set root `0`
>>> Lct.parent lct 0 -- under root `0`, parent of `0` is `Nothing`:
Nothing

>>> Lct.evert lct 0  -- set root `0`
>>> Lct.parent lct 1 -- under root `0`, parent of `1` is `0`:
Just 0

`link` / `cut`

Edges can be dynamically added (link) or removed (cut):

>>> -- 0  1  2
>>> --    +--3
>>> Lct.cut lct 0 1
>>> Lct.cut lct 1 2
>>> VU.generateM 4 (Lct.root lct)
[0,1,2,1]

>>> -- +-----+
>>> -- 0  1  2
>>> --    +--3
>>> Lct.link lct 0 2
>>> VU.generateM 4 (Lct.root lct)
[2,1,2,1]

Since: 1.1.1.0

Synopsis

data Lct s a = Lct {
- nLct :: !Int
- lLct :: !(MVector s Vertex)
- rLct :: !(MVector s Vertex)
- pLct :: !(MVector s Vertex)
- sLct :: !(MVector s Int)
- revLct :: !(MVector s Bit)
- vLct :: !(MVector s a)
- prodLct :: !(MVector s a)
- dualProdLct :: !(MVector s a)
- midLct :: !(MVector s a)
- subtreeProdLct :: !(MVector s a)
- invOpLct :: !(a -> a)
}
type Vertex = Int
new :: (PrimMonad m, Monoid a, Unbox a) => Int -> m (Lct (PrimState m) a)
newInv :: (PrimMonad m, Monoid a, Unbox a) => (a -> a) -> Int -> m (Lct (PrimState m) a)
build :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Vector a -> Vector (Vertex, Vertex) -> m (Lct (PrimState m) a)
buildInv :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => (a -> a) -> Vector a -> Vector (Vertex, Vertex) -> m (Lct (PrimState m) a)
read :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m a
write :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> a -> m ()
modify :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> (a -> a) -> Vertex -> m ()
modifyM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> (a -> m a) -> Vertex -> m ()
link :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m ()
cut :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m ()
evert :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m ()
expose :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m Vertex
expose_ :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m ()
root :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m Vertex
same :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m Bool
parent :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m (Maybe Vertex)
jump :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> Int -> m Vertex
jumpMaybe :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> Int -> m (Maybe Vertex)
lengthBetween :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m Vertex
lca :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m Vertex
lcaMaybe :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m (Maybe Vertex)
prodPath :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m a
prodSubtree :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m a
prodTree :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m a

Documentation

data Lct s a Source #

Link/cut tree.

Since: 1.1.1.0

Constructors

Lct

Fields

nLct :: !Int
The number of vertices.
Since: 1.1.1.0
lLct :: !(MVector s Vertex)
Decomposed node data storage: left children.
Since: 1.1.1.0
rLct :: !(MVector s Vertex)
Decomposed node data storage: right children.
Since: 1.1.1.0
pLct :: !(MVector s Vertex)
Decomposed node data storage: parents.
Since: 1.1.1.0
sLct :: !(MVector s Int)
Decomposed node data storage: subtree sizes.
Since: 1.1.1.0
revLct :: !(MVector s Bit)
Decomposed node data storage: reverse flags.
Since: 1.1.1.0
vLct :: !(MVector s a)
Decomposed node data storage: monoid values.
Since: 1.1.1.0
prodLct :: !(MVector s a)
Decomposed node data storage: monoid products.
Since: 1.1.1.0
dualProdLct :: !(MVector s a)
Decomposed node data storage: dual monoid products (right foldings). This is required for non-commutative monoids only.
Since: 1.1.1.0
midLct :: !(MVector s a)
Decomposed node data storage: path-parent monoid products. This works for subtree product queries over commutative monoids only.
Since: 1.1.1.0
subtreeProdLct :: !(MVector s a)
Decomposed node data storage: monoid product of subtree. This works for subtree product queries over commutative monoids only.
Since: 1.1.1.0
invOpLct :: !(a -> a)
Inverse operator of the monoid. This works for subtree product queries over commutative monoids only.
Since: 1.1.1.0

type Vertex = Int Source #

Alias of vertex type.

Constructors

new :: (PrimMonad m, Monoid a, Unbox a) => Int -> m (Lct (PrimState m) a) Source #

$O(n)$ Creates a link/cut tree with $n$ vertices and no edges. This setup disables subtree queries (prodSubtree).

Since: 1.1.1.0

newInv :: (PrimMonad m, Monoid a, Unbox a) => (a -> a) -> Int -> m (Lct (PrimState m) a) Source #

$O(n)$ Creates a link/cut tree with an inverse operator, initial monoid values and no edges. This setup enables subtree queries (prodSubtree).

Since: 1.1.1.0

build Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> Vector a	Vertex monoid values
-> Vector (Vertex, Vertex)	Edges
-> m (Lct (PrimState m) a)	Link/cut tree

$O(n + m \log n)$ Creates a link/cut tree of initial monoid values and initial edges. This setup disables subtree queries (prodSubtree).

Constraints

$0 \le u, v \lt n$

Since: 1.1.1.0

buildInv Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> (a -> a)	Inverse operator
-> Vector a	Vertex monoid values
-> Vector (Vertex, Vertex)	Edges
-> m (Lct (PrimState m) a)	Link/cut tree

$O(n + m \log n)$ Creates a link/cut tree with an inverse operator, initial monoid values and initial edges. This setup enables subtree queries (prodSubtree).

Constraints

$0 \le u, v \lt n$

Since: 1.1.1.0

Monoid value access

read :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m a Source #

$O(1)$ . Reads the monoid value on a vertex $v$ .

Constraints

$0 \le v \lt n$

Since: 1.5.1.0

write :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> a -> m () Source #

Amortized $O(\log n)$ . Writes to the monoid value of a vertex $v$ .

Constraints

$0 \le v \lt n$

Since: 1.1.1.0

modify :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> (a -> a) -> Vertex -> m () Source #

Amortized $O(\log n)$ . Given a user function $f$ , modifies the monoid value of a vertex $v$ .

Constraints

$0 \le v \lt n$

Since: 1.1.1.0

modifyM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> (a -> m a) -> Vertex -> m () Source #

Amortized $O(\log n)$ . Given a user function $f$ , modifies the monoid value of a vertex $v$ .

Constraints

$0 \le v \lt n$

Since: 1.1.1.0

Tree operations

Link/cut

link :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m () Source #

Amortized $O(\log n)$ . Creates an edge between $c$ and $p$ . In the represented tree, the $p$ will be the parent of $c$ .

Constraints

$0 \le c, p \lt n$
$u \ne v$
$c$ and $p$ are in different trees, otherwise the behavior is undefined.

Since: 1.1.1.0

cut :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m () Source #

Amortized $O(\log n)$ . Deletes an edge between $u$ and $v$ .

Constraints

$0 \le u, v \lt n$
$u \ne v$
There's an edge between $u$ and $v$ , otherwise the behavior is undefined.

Since: 1.1.1.0

Evert/expose

evert :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m () Source #

Amortized $O(\log n)$ . Makes $v$ a new root of the underlying tree.

Constraints

$0 \le v \lt n$

Since: 1.1.1.0

expose :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m Vertex Source #

Amortized $O(\log n)$ . Makes $v$ and the root to be in the same preferred path (auxiliary tree). After the operation, $v$ will be the new root and all the children will be detached from the preferred path.

Constraints

$0 \le v \lt n$

Since: 1.1.1.0

expose_ :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m () Source #

Amortized $O(\log n)$ . expose with the return value discarded.

Constraints

$0 \le v \lt n$

Since: 1.1.1.0

Tree queries

root :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m Vertex Source #

$O(\log n)$ Returns the root of the underlying tree.

Constraints

$0 \le v \lt n$

Since: 1.1.1.0

same :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m Bool Source #

$O(\log n)$ Returns whether the vertices $u$ and $v$ are in the same connected component (have the same root).

Constraints

$0 \le u, v \lt n$

Since: 1.5.1.0

parent :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> m (Maybe Vertex) Source #

$O(\log n)$ Returns the parent vertex in the underlying tree.

Constraints

$0 \le v \lt n$

Since: 1.1.1.0

jump :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> Int -> m Vertex Source #

$O(\log n)$ Given a path between $u$ and $v$ , returns the $k$ -th vertex from $u$ in the path.

Constraints

$0 \le u, v \lt n$
$0 \le k \lt \mathrm{|path|}$
$u$ and $v$ must be in the same connected component, otherwise the vehavior is undefined.

Since: 1.1.1.0

jumpMaybe :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> Int -> m (Maybe Vertex) Source #

$O(\log n)$ Given a path between $u$ and $v$ , returns the $k$ -th vertex from $u$ in the path.

Constraints

$0 \le u, v \lt n$
$u$ and $v$ must be in the same connected component, otherwise the vehavior is undefined.

Since: 1.5.1.0

lengthBetween :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m Vertex Source #

$O(\log n)$ Returns the length of path between $u$ and $v$ .

Constraints

$0 \le u, v \lt n$
$u$ and $v$ must be in the same connected component.

Since: 1.5.1.0

lca :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m Vertex Source #

$O(\log n)$ Returns the LCA of $u$ and $v$ . Because the root of the underlying tree changes in almost every operation, one might want to use evert beforehand.

Constraints

$0 \le u, v \lt n$
$u$ and $v$ must be in the same connected component.

Since: 1.1.1.0

lcaMaybe :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m (Maybe Vertex) Source #

$O(\log n)$ Returns the LCA of $u$ and $v$ . Because the root of the underlying tree changes in almost every operation, one might want to use evert beforehand.

Constraints

$0 \le u, v \lt n$

Since: 1.5.1.0

Monoid products

prodPath :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> m a Source #

Amortized $O(\log n)$ . Folds a path between $u$ and $v$ (inclusive).

Constraints

$0 \le u, v \lt n$
$u$ and $v$ must be in the same connected component, otherwise the return value is nonsense.

Since: 1.1.1.0

prodSubtree Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> Lct (PrimState m) a	Link/cut tree
-> Vertex	Vertex $v$
-> Vertex	Parent $p$ (not need be adjacent to $v$ ), or same as $v$ , making it a new root.
-> m a	Subtree's monoid product

Amortized $O(\log n)$ . Fold the subtree under $v$ , considering $p$ as the root-side vertex. Or, if $p$ equals $v$ , $v$ will be the new root.

Constraints

The inverse operator must be set on construction (newInv or buildInv).
$0 \le u, v \lt n$

Since: 1.1.1.0

prodTree Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> Lct (PrimState m) a	Link/cut tree
-> Vertex	Vertex $v$
-> m a	Subtree's monoid product

Amortized $O(\log n)$ . Fold a tree that contains $v$ .

Constraints

The inverse operator must be set on construction (newInv or buildInv).
$0 \le v \lt n$

Since: 1.5.1.0

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result

Example

prodPath, prodSubtree, prodTree

lca, jump, lengthBetween

parent

link / cut

Documentation

Constructors

Constraints

Constraints

Monoid value access

Constraints

Constraints

Constraints

Constraints

Tree operations

Link/cut

Constraints

Constraints

Evert/expose

Constraints

Constraints

Constraints

Tree queries

Constraints

Constraints

Constraints

Constraints

Constraints

Constraints

Constraints

Constraints

Monoid products

Constraints

Constraints

Constraints

`prodPath`, `prodSubtree`, `prodTree`

`lca`, `jump`, `lengthBetween`

`parent`

`link` / `cut`