tpl_link_cut_tree.H File Reference

Link-Cut Tree: a dynamic forest with path queries. More...

#include <concepts>
#include <initializer_list>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>
#include <tpl_array.H>
#include <tpl_arrayStack.H>
#include <tpl_tree_node.H>
#include <ah-errors.H>

Include dependency graph for tpl_link_cut_tree.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::DefaultMonoid< T >
	Default (no-op) monoid for connectivity-only usage. More...
struct	Aleph::SumMonoid< T >
	Sum monoid: identity = 0, combine = a + b. More...
struct	Aleph::MinMonoid< T >
	Min monoid: identity = numeric max, combine = min(a, b). More...
struct	Aleph::MaxMonoid< T >
	Max monoid: identity = numeric lowest, combine = max(a, b). More...
struct	Aleph::XorMonoid< T >
	XOR monoid: identity = 0, combine = a ^ b. More...
struct	Aleph::GcdMonoid< T >
	GCD monoid: identity = 0 (since gcd(0, x) = x), combine = gcd. More...
struct	Aleph::ProductMonoid< T >
	Product monoid: identity = 1, combine = a * b. More...
struct	Aleph::NoLazyTag< T >
	No-op lazy tag (default — no deferred path updates). More...
struct	Aleph::AddLazyTag< T >
	Additive lazy tag: adds a delta to every node on a path. More...
struct	Aleph::AssignLazyTag< T >
	Assignment lazy tag: sets every node on a path to a fixed value. More...
struct	Aleph::AssignLazyTag< T >::tag_type
	Payload for the assignment lazy tag. More...
struct	Aleph::monoid_supports_counted_lazy< Monoid, class >
	Metafunction to check if a monoid supports counted lazy tags. More...
struct	Aleph::monoid_supports_counted_lazy< Monoid, std::void_t< typename Monoid::supports_counted_lazy > >
	Specialization for monoids with supports_counted_lazy member. More...
struct	Aleph::is_counted_lazy_tag< LazyTag, T >
	Metafunction to check if a tag is a counted lazy tag. More...
struct	Aleph::is_counted_lazy_tag< AddLazyTag< T >, T >
	Specialization for AddLazyTag. More...
struct	Aleph::is_counted_lazy_tag< AssignLazyTag< T >, T >
	Specialization for AssignLazyTag. More...
class	Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >
	Dynamic forest with path queries via Link-Cut Trees. More...
struct	Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node
	Internal node of the Link-Cut Tree (opaque handle). More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Concepts
concept	Aleph::LCTMonoid
	Concept for a monoidal combiner over path values.
concept	Aleph::LCTLazyTag
	Concept for a lazy-tag policy used in deferred path updates.

Typedefs
using	Aleph::Link_Cut_Tree = Gen_Link_Cut_Tree< int >
	Convenience alias for a connectivity-only Link-Cut Tree.

Detailed Description

Link-Cut Tree: a dynamic forest with path queries.

A Link-Cut Tree (Sleator & Tarjan, 1983) is a powerful data structure that maintains a forest of rooted trees. It supports dynamic modifications (adding and removing edges) and queries on paths (such as the sum, minimum, maximum, or generic aggregation of node values along a path), all in amortized \(O(\log n)\) time per operation.

Theoretical Background

The trees in the forest (called represented trees) are decomposed into vertex-disjoint preferred paths. Each preferred path is stored as a Splay Tree (called an auxiliary tree), keyed by depth in the represented tree. This means an in-order traversal of the Splay Tree yields the path from the highest node (closest to the root) to the lowest. The root of each auxiliary tree contains a pointer to the parent of the highest node in the path it represents (called a path-parent pointer).

Main Operations

• link(u, v) — Merges two trees by making u a child of v.
• cut(u, v) — Splits a tree by removing the edge between u and v.
• make_root(x) — Reroots the represented tree containing x so that x becomes the root.
• find_root(x) — Finds the root of the tree containing x.
• connected(u, v) — Checks if u and v are in the same tree.
• lca(u, v) — Finds the lowest common ancestor of u and v.
• path_query(u, v) — Computes the aggregate value over the path between u and v.
• path_apply(u, v, tag) — Applies a lazy update to all nodes on the path between u and v.

Genericity and Concepts

The structure is heavily customizable using C++20 concepts:

• T: The value type stored at each node.
• Monoid: A type satisfying LCTMonoid, dictating how node values are aggregated (e.g., Sum, Min, Max).
• LazyTag: A type satisfying LCTLazyTag, dictating how range updates (like adding a delta to a path) are applied lazily.

Author

Leandro Rabindranath León

Definition in file tpl_link_cut_tree.H.