Template Class RangeMinimum

• Defined in File RangeMinimum.h

Class Documentation

template<class T, class Compare = std::less<T>>
class RangeMinimum

the range minima of an array by Bender and Farach-Colton: the Cartesian tree, its Euler tour, and the minima of the depths along the tour

Public Types

using value_type = T

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using const_reference = const T&

using reference = const_reference

using const_iterator = typename std::vector<T>::const_iterator

using iterator = const_iterator

Public Functions

RangeMinimum(void) = default

explicit RangeMinimum(std::vector<T> A, Compare less = {})

the structure of A, O( n )

std::size_t query(std::size_t i, std::size_t j) const

the place of the leftmost minimum of A[ i .

. j ], O( 1 )

Pre:

i <= j < size()

Post:

a leftmost minimum of A[ i .. j ] (an audit)

inline std::size_t size(void) const

const T &operator[](std::size_t i) const

Pre:

i < size()

inline const std::vector<std::size_t> &eulerTour(void) const

the nodes of the Euler tour of the Cartesian tree, 2 n - 1 of them

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const