Aleph::Cartesian_Tree_RMQ< T > Struct Template Reference

Range minimum queries via Cartesian Tree. More...

#include <tpl_cartesian_tree.H>

Inheritance diagram for Aleph::Cartesian_Tree_RMQ< T >:

Collaboration diagram for Aleph::Cartesian_Tree_RMQ< T >:

Public Types
using	Base = Gen_Cartesian_Tree_RMQ< T, Aleph::less< T > >
Public Types inherited from Aleph::Gen_Cartesian_Tree_RMQ< T, Aleph::less< T > >
using	Item_Type = T
	The type of the element.

Additional Inherited Members
Public Member Functions inherited from Aleph::Gen_Cartesian_Tree_RMQ< T, Aleph::less< T > >
	Gen_Cartesian_Tree_RMQ (const Array< T > &values, Aleph::less< T > c=Aleph::less< T >())
	Construct from an Array<T>.
	Gen_Cartesian_Tree_RMQ (const std::vector< T > &values, Aleph::less< T > c=Aleph::less< T >())
	Construct from a std::vector<T>.
	Gen_Cartesian_Tree_RMQ (std::initializer_list< T > il, Aleph::less< T > c=Aleph::less< T >())
	Construct from an initializer_list<T>.
	Gen_Cartesian_Tree_RMQ (const DynList< T > &values, Aleph::less< T > c=Aleph::less< T >())
	Construct from a DynList<T>.
	Gen_Cartesian_Tree_RMQ (const size_t num, const T &init, Aleph::less< T > c=Aleph::less< T >())
	Construct with num elements all equal to init.
T	query (const size_t l, const size_t r) const
	Range query over [l, r] in O(1).
size_t	query_idx (const size_t l, const size_t r) const
	Return the index of the optimal element in a[l..r].
T	get (const size_t i) const
	Retrieve the value at position i in O(1).
constexpr size_t	size () const noexcept
	Number of elements.
constexpr bool	is_empty () const noexcept
	True if empty.
Array< T >	values () const
	Copy of the original values.
const Gen_Euler_Tour_LCA< T, Aleph::less< T > > &	lca_engine () const noexcept
	Const reference to the internal LCA engine.

Detailed Description

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

Range minimum queries via Cartesian Tree.

Template Parameters

T	a totally ordered type.

Definition at line 937 of file tpl_cartesian_tree.H.

Member Typedef Documentation

Base

template<std::totally_ordered T>

using Aleph::Cartesian_Tree_RMQ< T >::Base = Gen_Cartesian_Tree_RMQ<T, Aleph::less<T> >

Definition at line 940 of file tpl_cartesian_tree.H.

---

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

• tpl_cartesian_tree.H