pixie::rmq::SparseTable< T, Compare, Index, Alignment > Class Template Reference

Static sparse-table RMQ baseline. More...

#include <sparse_table.h>

Inheritance diagram for pixie::rmq::SparseTable< T, Compare, Index, Alignment >:

Public Member Functions
	SparseTable ()=default
	Construct an empty sparse table.
	SparseTable (std::span< const T > values, Compare compare=Compare())
	Build a sparse table over values.
std::size_t	size_impl () const
	Return the number of indexed values.
T	value_at_impl (std::size_t position) const
	Return the value at an indexed position.
std::size_t	arg_min_impl (std::size_t left, std::size_t right) const
	Return the first minimum position in [left, right).
std::size_t	memory_usage_bytes_impl () const
	Return owned auxiliary memory usage in bytes.
Public Member Functions inherited from pixie::rmq::RmqBase< Impl, Value >
std::size_t	size () const
	Number of indexed values.
bool	empty () const
	Whether the indexed array is empty.
std::size_t	arg_min (std::size_t left, std::size_t right) const
	Return the first minimum position in [left, right).
Value	range_min (std::size_t left, std::size_t right) const
	Return the minimum value in [left, right).
std::size_t	memory_usage_bytes () const
	Return owned auxiliary memory usage in bytes when implemented.

Static Public Attributes
static constexpr std::size_t	npos
static constexpr Index	invalid_index = std::numeric_limits<Index>::max()
Static Public Attributes inherited from pixie::rmq::RmqBase< Impl, Value >
static constexpr std::size_t	npos = std::numeric_limits<std::size_t>::max()
	Sentinel returned when no valid query answer exists.

Detailed Description

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t Alignment = pixie::kAlignedStorageLineBytes>
class pixie::rmq::SparseTable< T, Compare, Index, Alignment >

Static sparse-table RMQ baseline.

Stores the index of the first minimum for each power-of-two range. Query time is O(1), build time is O(n log n), and storage is O(n log n) indices. The indexed values are not owned and must outlive this object.

Template Parameters

T	Value type in the indexed array.
Compare	Strict weak ordering used to choose minima.
Index	Unsigned integer type used for stored positions.
Alignment	Byte alignment for each sparse-table level allocation. Use 0 to select the standard allocator.

Constructor & Destructor Documentation

SparseTable()

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t Alignment = pixie::kAlignedStorageLineBytes>

pixie::rmq::SparseTable< T, Compare, Index, Alignment >::SparseTable ( std::span< const T > values, Compare compare = Compare() )

inlineexplicit

Build a sparse table over values.

The values are not copied and must outlive this object. Equal values keep the smaller index as the RMQ answer.

Parameters

values	Values to index.
compare	Ordering used to choose minima.

Exceptions

std::length_error

if Index cannot represent all positions.

Member Function Documentation

arg_min_impl()

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t Alignment = pixie::kAlignedStorageLineBytes>

std::size_t pixie::rmq::SparseTable< T, Compare, Index, Alignment >::arg_min_impl ( std::size_t left, std::size_t right ) const

inline

Return the first minimum position in [left, right).

Answers in O(1) by comparing the two power-of-two ranges covering the half-open query interval. Ties return the smaller position.

Parameters

left	First position in the query range.
right	One past the last position in the query range.

Returns

Zero-based position of the first range minimum, or npos.

memory_usage_bytes_impl()

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t Alignment = pixie::kAlignedStorageLineBytes>

std::size_t pixie::rmq::SparseTable< T, Compare, Index, Alignment >::memory_usage_bytes_impl ( ) const

inline

Return owned auxiliary memory usage in bytes.

Counts this sparse-table object and all stored index levels. The external input values are not owned and are excluded.

size_impl()

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t Alignment = pixie::kAlignedStorageLineBytes>

std::size_t pixie::rmq::SparseTable< T, Compare, Index, Alignment >::size_impl ( ) const

inline

Return the number of indexed values.

Returns

values.size() from construction.

value_at_impl()

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t Alignment = pixie::kAlignedStorageLineBytes>

T pixie::rmq::SparseTable< T, Compare, Index, Alignment >::value_at_impl ( std::size_t position ) const

inline

Return the value at an indexed position.

Parameters

position

Zero-based position in the indexed values.

Returns

Copy of the value at position.

Member Data Documentation

npos

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t Alignment = pixie::kAlignedStorageLineBytes>

std::size_t pixie::rmq::SparseTable< T, Compare, Index, Alignment >::npos

staticconstexpr

Initial value:

=
      RmqBase<SparseTable<T, Compare, Index, Alignment>, T>::npos

---

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

• include/pixie/rmq/sparse_table.h