Aleph::Sparse_Table< T > Struct Template Reference

Sparse Table for range minimum queries. More...

#include <tpl_sparse_table.H>

Inheritance diagram for Aleph::Sparse_Table< T >:

Collaboration diagram for Aleph::Sparse_Table< T >:

Public Types
using	Base = Gen_Sparse_Table< T, Min_Op< T > >
Public Types inherited from Aleph::Gen_Sparse_Table< T, Min_Op< T > >
using	Item_Type = T
	The type of the element stored in the table.

Additional Inherited Members
Public Member Functions inherited from Aleph::Gen_Sparse_Table< T, Min_Op< T > >
	Gen_Sparse_Table (const size_t num, const T &init_val, Min_Op< T > oper=Min_Op< T >())
	Construct a sparse table with num elements, all equal to init_val.
	Gen_Sparse_Table (std::initializer_list< T > il, Min_Op< T > oper=Min_Op< T >())
	Construct from an initializer list in O(n log n) time.
	Gen_Sparse_Table (const Array< T > &values, Min_Op< T > oper=Min_Op< T >())
	Construct from an Array<T> in O(n log n) time.
	Gen_Sparse_Table (const std::vector< T > &values, Min_Op< T > oper=Min_Op< T >())
	Construct from a std::vector<T> in O(n log n) time.
	Gen_Sparse_Table (const DynList< T > &values, Min_Op< T > oper=Min_Op< T >())
	Construct from a DynList<T> in O(n log n) time.
	Gen_Sparse_Table (const Gen_Sparse_Table &)=default
	Gen_Sparse_Table (Gen_Sparse_Table &&) noexcept(std::is_nothrow_move_constructible_v< Array< T > > &&std::is_nothrow_move_constructible_v< Min_Op< T > >)=default
Gen_Sparse_Table &	operator= (const Gen_Sparse_Table &)=default
Gen_Sparse_Table &	operator= (Gen_Sparse_Table &&) noexcept(std::is_nothrow_move_assignable_v< Array< T > > &&std::is_nothrow_move_assignable_v< Min_Op< T > >)=default
T	query (const size_t l, const size_t r) const
	Range query over [l, r] in O(1).
T	get (const size_t i) const
	Retrieve the value a[i] in O(1).
constexpr size_t	size () const noexcept
	Number of logical elements.
constexpr bool	is_empty () const noexcept
	True if the table contains no elements.
constexpr size_t	num_levels () const noexcept
	Number of precomputed levels (floor(log2(n)) + 1).
Array< T >	values () const
	Reconstruct all original values into an Array.
void	swap (Gen_Sparse_Table &other) noexcept
	Swap this table with other in O(1).

Detailed Description

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

Sparse Table for range minimum queries.

Convenient specialisation of Gen_Sparse_Table using Min_Op<T> for O(1) range minimum queries on a static array.

Template Parameters

T	a totally ordered type.

Example

Sparse_Table<int> st = {5, 2, 4, 7, 1, 3, 6};
assert(st.query(0, 3) == 2);  // min(5, 2, 4, 7)
assert(st.query(2, 6) == 1);  // min(4, 7, 1, 3, 6)
assert(st.query(4, 4) == 1);  // min(1)

Definition at line 427 of file tpl_sparse_table.H.

Member Typedef Documentation

Base

template<std::totally_ordered T>

using Aleph::Sparse_Table< T >::Base = Gen_Sparse_Table<T, Min_Op<T> >

Definition at line 430 of file tpl_sparse_table.H.

---

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

• tpl_sparse_table.H