Lowest Common Ancestor queries in O(1) via Euler Tour reduction to RMQ on a Cartesian Tree. More...

Inheritance diagram for Aleph::Gen_Euler_Tour_LCA< T, Comp >:

Collaboration diagram for Aleph::Gen_Euler_Tour_LCA< T, Comp >:

Classes
struct	DepthEntry
	Entry for the depth-based Sparse Table: (depth, euler_node_index). More...

struct	DepthMinOp
	Min-op on DepthEntry: compares by depth. More...

Public Member Functions
	Gen_Euler_Tour_LCA (const Array< T > &values, Comp c=Comp())
	Construct from an Array<T>.

	Gen_Euler_Tour_LCA (const std::vector< T > &values, Comp c=Comp())
	Construct from a std::vector<T>.

	Gen_Euler_Tour_LCA (std::initializer_list< T > il, Comp c=Comp())
	Construct from an initializer_list<T>.

	Gen_Euler_Tour_LCA (const DynList< T > &values, Comp c=Comp())
	Construct from a DynList<T>.

	Gen_Euler_Tour_LCA (const size_t num, const T &init, Comp c=Comp())
	Construct with `num` elements all equal to `init`.

size_t	lca (const size_t u, const size_t v) const
	Lowest Common Ancestor of nodes `u` and `v` in O(1).

size_t	depth_of (const size_t u) const
	Depth of node `u` in the Cartesian Tree.

size_t	distance (const size_t u, const size_t v) const
	Distance between nodes `u` and `v` in the tree.

constexpr size_t	size () const noexcept
	Number of nodes.

constexpr bool	is_empty () const noexcept
	True if empty.

const Gen_Cartesian_Tree< T, Comp > &	tree () const noexcept
	Const reference to the internal Cartesian Tree.

Array< size_t >	euler_tour () const
	Copy of the Euler Tour array (for inspection/debugging).

size_t	euler_tour_size () const noexcept
	Size of the Euler Tour (should be 2n-1 for n > 0).

Private Member Functions
void	build_euler_tour ()
	Build Euler Tour iteratively using an explicit stack with phases.

void	build_sparse_table ()
	Build the Sparse Table over the depth entries.

Private Attributes
Gen_Cartesian_Tree< T, Comp >	tree_

Array< size_t >	euler_

Array< size_t >	depth_arr_

Array< size_t >	first_

Array< size_t >	node_depth_

Gen_Sparse_Table< DepthEntry, DepthMinOp >	sparse_

size_t	euler_size_

Detailed Description

template<typename T, class Comp>
requires StrictWeakOrder<Comp, T>
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.

Given an array, this class:

Builds a Cartesian Tree in O(n).
Performs an Euler Tour of the tree, producing euler[] (2n-1 node visits) and depth[] arrays.
Builds a Sparse Table over the depth array for O(1) RMQ.

The LCA of two nodes u, v corresponds to the minimum-depth node in the Euler Tour between the first occurrences of u and v.

Template Parameters

T	element type.
Comp	comparator for the Cartesian Tree heap property.

Example: Euler_Tour_LCA<int> lca = {3, 2, 6, 1, 9};

size_t ancestor = lca.lca(0, 2); // LCA of positions 0 and 2

Aleph::Gen_Euler_Tour_LCA::lca
size_t lca(const size_t u, const size_t v) const
Lowest Common Ancestor of nodes u and v in O(1).
Definition tpl_cartesian_tree.H:703

Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Aleph::Euler_Tour_LCA
LCA on a min-heap Cartesian Tree.
Definition tpl_cartesian_tree.H:780