Aleph::Euler_Tour_LCA< T > Struct Template Reference

LCA on a min-heap Cartesian Tree. More...

#include <tpl_cartesian_tree.H>

Inheritance diagram for Aleph::Euler_Tour_LCA< T >:

Collaboration diagram for Aleph::Euler_Tour_LCA< T >:

Public Types
using	Base = Gen_Euler_Tour_LCA< T, Aleph::less< T > >

Additional Inherited Members
Public Member Functions inherited from Aleph::Gen_Euler_Tour_LCA< T, Aleph::less< T > >
	Gen_Euler_Tour_LCA (const Array< T > &values, Aleph::less< T > c=Aleph::less< T >())
	Construct from an Array<T>.
	Gen_Euler_Tour_LCA (const std::vector< T > &values, Aleph::less< T > c=Aleph::less< T >())
	Construct from a std::vector<T>.
	Gen_Euler_Tour_LCA (std::initializer_list< T > il, Aleph::less< T > c=Aleph::less< T >())
	Construct from an initializer_list<T>.
	Gen_Euler_Tour_LCA (const DynList< T > &values, Aleph::less< T > c=Aleph::less< T >())
	Construct from a DynList<T>.
	Gen_Euler_Tour_LCA (const size_t num, const T &init, Aleph::less< T > c=Aleph::less< T >())
	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, Aleph::less< T > > &	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).

Detailed Description

template<std::totally_ordered T>
struct Aleph::Euler_Tour_LCA< T >

LCA on a min-heap Cartesian Tree.

Template Parameters

T	a totally ordered type.

Definition at line 778 of file tpl_cartesian_tree.H.

Member Typedef Documentation

Base

template<std::totally_ordered T>

using Aleph::Euler_Tour_LCA< T >::Base = Gen_Euler_Tour_LCA<T, Aleph::less<T> >

Definition at line 781 of file tpl_cartesian_tree.H.

---

The documentation for this struct was generated from the following file:

• tpl_cartesian_tree.H