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

Static iterative segment-tree RMQ baseline. More...

#include <segment_tree.h>

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

Public Member Functions
	SegmentTree ()=default
	Construct an empty segment tree.
	SegmentTree (std::span< const T > values, Compare compare=Compare())
	Build an iterative segment tree 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>
class pixie::rmq::SegmentTree< T, Compare, Index >

Static iterative segment-tree RMQ baseline.

Stores the index of the first minimum for each segment in a flat binary tree. Query time is O(log n), build time is O(n), and storage is O(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.

Constructor & Destructor Documentation

SegmentTree()

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

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

inlineexplicit

Build an iterative segment tree 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 pixie::rmq::SegmentTree< T, Compare, Index >::arg_min_impl ( std::size_t left, std::size_t right ) const

inline

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

Answers in O(log n) by walking the flat iterative segment tree. 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 pixie::rmq::SegmentTree< T, Compare, Index >::memory_usage_bytes_impl ( ) const

inline

Return owned auxiliary memory usage in bytes.

Counts this segment-tree object and its flat index buffer. 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 pixie::rmq::SegmentTree< T, Compare, Index >::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>

T pixie::rmq::SegmentTree< T, Compare, Index >::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 pixie::rmq::SegmentTree< T, Compare, Index >::npos

staticconstexpr

Initial value:

=
      RmqBase<SegmentTree<T, Compare, Index>, T>::npos

---

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

• include/pixie/rmq/segment_tree.h