tpl_cartesian_tree.H File Reference

Cartesian Tree, LCA via Euler Tour, and RMQ via Cartesian Tree. More...

#include <cassert>
#include <cstddef>
#include <concepts>
#include <initializer_list>
#include <type_traits>
#include <utility>
#include <vector>
#include <tpl_array.H>
#include <tpl_dynList.H>
#include <tpl_sparse_table.H>
#include <ahFunction.H>
#include <ah-errors.H>
#include <ah-concepts.H>

Include dependency graph for tpl_cartesian_tree.H:

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

Go to the source code of this file.

Classes
class	Aleph::Gen_Cartesian_Tree< T, Comp >
	Explicit Cartesian Tree built in O(n) with a monotonic stack. More...
struct	Aleph::Cartesian_Tree< T >
	Cartesian Tree for min-heap (range minimum). More...
struct	Aleph::Max_Cartesian_Tree< T >
	Cartesian Tree for max-heap (range maximum). More...
class	Aleph::Gen_Euler_Tour_LCA< T, Comp >
	Lowest Common Ancestor queries in O(1) via Euler Tour reduction to RMQ on a Cartesian Tree. More...
struct	Aleph::Gen_Euler_Tour_LCA< T, Comp >::DepthEntry
	Entry for the depth-based Sparse Table: (depth, euler_node_index). More...
struct	Aleph::Gen_Euler_Tour_LCA< T, Comp >::DepthMinOp
	Min-op on DepthEntry: compares by depth. More...
struct	Aleph::Euler_Tour_LCA< T >
	LCA on a min-heap Cartesian Tree. More...
struct	Aleph::Max_Euler_Tour_LCA< T >
	LCA on a max-heap Cartesian Tree. More...
class	Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >
	O(1) static range queries via the Cartesian Tree reduction. More...
struct	Aleph::Cartesian_Tree_RMQ< T >
	Range minimum queries via Cartesian Tree. More...
struct	Aleph::Cartesian_Tree_RMaxQ< T >
	Range maximum queries via Cartesian Tree. More...

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

Detailed Description

Cartesian Tree, LCA via Euler Tour, and RMQ via Cartesian Tree.

This file implements the classic chain of reductions:

RMQ  <-->  LCA  <-->  Cartesian Tree

Three class templates are provided:

• Gen_Cartesian_Tree<T, Comp> — Explicit Cartesian Tree built in O(n) with a monotonic stack. The tree satisfies the heap property under Comp and the inorder traversal reproduces the original array.
• Gen_Euler_Tour_LCA<T, Comp> — Lowest Common Ancestor in O(1) via Euler Tour + Sparse Table on the Cartesian Tree.
• Gen_Cartesian_Tree_RMQ<T, Comp> — O(1) static range queries via the reduction RMQ -> LCA -> Cartesian Tree.

Complexity

Class	Build	Query	Space
Gen_Cartesian_Tree	O(n)	—	O(n)
Gen_Euler_Tour_LCA	O(n log n)*	O(1)	O(n log n)*
Gen_Cartesian_Tree_RMQ	O(n log n)*	O(1)	O(n log n)*

*Dominated by the internal Sparse Table.

See also

tpl_sparse_table.H Sparse Table for static O(1) range queries.

tpl_segment_tree.H Dynamic range queries with updates.

tpl_fenwick_tree.H Prefix-based range queries.

Author

Leandro Rabindranath León

Definition in file tpl_cartesian_tree.H.