Aleph::Gen_Cartesian_Tree_RMQ< T, Comp > Class Template Reference

O(1) static range queries via the Cartesian Tree reduction. More...

#include <tpl_cartesian_tree.H>

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

Public Types
using	Item_Type = T
	The type of the element.

Public Member Functions
	Gen_Cartesian_Tree_RMQ (const Array< T > &values, Comp c=Comp())
	Construct from an Array<T>.
	Gen_Cartesian_Tree_RMQ (const std::vector< T > &values, Comp c=Comp())
	Construct from a std::vector<T>.
	Gen_Cartesian_Tree_RMQ (std::initializer_list< T > il, Comp c=Comp())
	Construct from an initializer_list<T>.
	Gen_Cartesian_Tree_RMQ (const DynList< T > &values, Comp c=Comp())
	Construct from a DynList<T>.
	Gen_Cartesian_Tree_RMQ (const size_t num, const T &init, Comp c=Comp())
	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, Comp > &	lca_engine () const noexcept
	Const reference to the internal LCA engine.

Private Attributes
Gen_Euler_Tour_LCA< T, Comp >	lca_

Detailed Description

template<typename T, class Comp>
requires StrictWeakOrder<Comp, T>
class Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >

O(1) static range queries via the Cartesian Tree reduction.

Wraps Gen_Euler_Tour_LCA and exposes a range query interface compatible with Gen_Sparse_Table:

query(l, r) returns the optimal value in a[l..r] under Comp. query_idx(l, r) returns the index of that optimal value.

The key insight: RMQ(l, r) = data_at(LCA(l, r)) because the Cartesian Tree's root in any subrange is the position of the optimal element.

Template Parameters

T	element type.
Comp	comparator for the heap property.

Example

Cartesian_Tree_RMQ<int> rmq = {5, 2, 4, 7, 1, 3, 6};
assert(rmq.query(0, 3) == 2);  // min(5, 2, 4, 7)
assert(rmq.query(2, 6) == 1);  // min(4, 7, 1, 3, 6)
assert(rmq.query_idx(2, 6) == 4);  // index of min

Definition at line 829 of file tpl_cartesian_tree.H.

Member Typedef Documentation

Item_Type

template<typename T , class Comp >

using Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::Item_Type = T

The type of the element.

Definition at line 835 of file tpl_cartesian_tree.H.

Constructor & Destructor Documentation

Gen_Cartesian_Tree_RMQ() [1/5]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::Gen_Cartesian_Tree_RMQ ( const Array< T > &  values, Comp  c = Comp()  )

inline

Construct from an Array<T>.

Definition at line 838 of file tpl_cartesian_tree.H.

Gen_Cartesian_Tree_RMQ() [2/5]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::Gen_Cartesian_Tree_RMQ ( const std::vector< T > &  values, Comp  c = Comp()  )

inline

Construct from a std::vector<T>.

Definition at line 842 of file tpl_cartesian_tree.H.

Gen_Cartesian_Tree_RMQ() [3/5]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::Gen_Cartesian_Tree_RMQ ( std::initializer_list< T >  il, Comp  c = Comp()  )

inline

Construct from an initializer_list<T>.

Definition at line 846 of file tpl_cartesian_tree.H.

Gen_Cartesian_Tree_RMQ() [4/5]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::Gen_Cartesian_Tree_RMQ ( const DynList< T > &  values, Comp  c = Comp()  )

inline

Construct from a DynList<T>.

Definition at line 850 of file tpl_cartesian_tree.H.

Gen_Cartesian_Tree_RMQ() [5/5]

template<typename T , class Comp >

Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::Gen_Cartesian_Tree_RMQ ( const size_t  num, const T &  init, Comp  c = Comp()  )

inline

Construct with num elements all equal to init.

Definition at line 854 of file tpl_cartesian_tree.H.

Member Function Documentation

get()

template<typename T , class Comp >

T Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::get ( const size_t  i ) const

inline

Retrieve the value at position i in O(1).

Parameters

i	0-based index into the original array.

Returns

Copy of the value stored at index i.

Exceptions

std::out_of_range

if i >= size().

Definition at line 902 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::lca_.

is_empty()

template<typename T , class Comp >

constexpr bool Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::is_empty ( ) const

inlineconstexprnoexcept

True if empty.

Definition at line 914 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::lca_.

lca_engine()

template<typename T , class Comp >

const Gen_Euler_Tour_LCA< T, Comp > & Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::lca_engine ( ) const

inlinenoexcept

Const reference to the internal LCA engine.

Definition at line 926 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::lca_.

query()

template<typename T , class Comp >

T Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::query ( const size_t  l, const size_t  r  ) const

inline

Range query over [l, r] in O(1).

Returns the optimal value (min or max depending on Comp) in positions l..r of the original array.

Parameters

l	0-based left index (inclusive).
r	0-based right index (inclusive).

Exceptions

std::out_of_range

if l > r or r >= size().

Definition at line 867 of file tpl_cartesian_tree.H.

References ah_out_of_range_error_if, l, Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::lca_, r, and Aleph::HTList::size().

query_idx()

template<typename T , class Comp >

size_t Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::query_idx ( const size_t  l, const size_t  r  ) const

inline

Return the index of the optimal element in a[l..r].

Parameters

l	0-based left index (inclusive).
r	0-based right index (inclusive).

Exceptions

std::out_of_range

if l > r or r >= size().

When the optimal value occurs multiple times in the range, this returns the leftmost occurrence (stable tie-break).

Definition at line 886 of file tpl_cartesian_tree.H.

References ah_out_of_range_error_if, l, Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::lca_, r, and Aleph::HTList::size().

Referenced by TEST().

size()

template<typename T , class Comp >

constexpr size_t Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::size ( ) const

inlineconstexprnoexcept

Number of elements.

Definition at line 908 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::lca_.

values()

template<typename T , class Comp >

Array< T > Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::values ( ) const

inline

Copy of the original values.

Definition at line 920 of file tpl_cartesian_tree.H.

References Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::lca_.

Member Data Documentation

lca_

template<typename T , class Comp >

Gen_Euler_Tour_LCA<T, Comp> Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::lca_

private

Definition at line 831 of file tpl_cartesian_tree.H.

Referenced by Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::get(), Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::is_empty(), Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::lca_engine(), Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::query(), Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::query_idx(), Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::size(), and Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::values().

---

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

• tpl_cartesian_tree.H