Template Class SparseTable

• Defined in File RangeMinimum.h

Class Documentation

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

the range minima of an array by the sparse table

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

SparseTable(void) = default

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

the table of A, O( n log 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_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const