cplib::RangeMinQuery< T, Comp > Class Template Reference

Efficient \(\langle O(N), O(1) \rangle\) static range minimum query. More...

#include <rmq.hpp>

Public Types
using	size_type = std::size_t

Public Member Functions
	RangeMinQuery ()=default
	Creates an empty RangeMinQuery.
	RangeMinQuery (const std::vector< T > &arr)
	Construct the range minumum query object from the given sequence.
	RangeMinQuery (std::vector< T > &&arr)
	Construct the range minumum query object from the given sequence.
template<typename InputIt >
	RangeMinQuery (InputIt first, InputIt last)
	Construct the range minumum query object from the given sequence.
size_type	size () const
	Returns number of elements in the sequence.
T	range_min (size_type left, size_type right) const
	Returns the minimum element in the 0-based half-open range [left, right).

Static Public Attributes
static constexpr int	block_size = impl::RangeMinBlock::bitmap_size

Detailed Description

template<typename T, typename Comp = std::less<T>>
class cplib::RangeMinQuery< T, Comp >

Efficient \(\langle O(N), O(1) \rangle\) static range minimum query.

Divides input sequence into machine word sized blocks. Uses bit operations for in-block queries, and SparseTable for inter-block queries. Under the transdichotomous model ( \(w\geq\log_2 N\) where \(w=64\) is the word size), initialization takes \(O(N)\) time.

Template Parameters

T	Type of elements.
Comp	Comparison function type that is passed to std::min. Must satisfy C++ named requirement Compare.

Constructor & Destructor Documentation

RangeMinQuery() [1/3]

template<typename T , typename Comp = std::less<T>>

cplib::RangeMinQuery< T, Comp >::RangeMinQuery ( const std::vector< T > &  arr )

inline

Construct the range minumum query object from the given sequence.

Makes \(O(N)\) calls to Comp and creates \(O(N)\) copies of sequence elements along with \(O(N)\) integers as bit masks.

RangeMinQuery() [2/3]

template<typename T , typename Comp = std::less<T>>

cplib::RangeMinQuery< T, Comp >::RangeMinQuery ( std::vector< T > &&  arr )

inline

Construct the range minumum query object from the given sequence.

Makes \(O(N)\) calls to Comp and creates \(O(N)\) copies of sequence elements along with \(O(N)\) integers as bit masks.

RangeMinQuery() [3/3]

template<typename T , typename Comp = std::less<T>>

template<typename InputIt >

cplib::RangeMinQuery< T, Comp >::RangeMinQuery ( InputIt  first, InputIt  last  )

inline

Construct the range minumum query object from the given sequence.

Makes \(O(N)\) calls to Comp and creates \(O(N)\) copies of sequence elements along with \(O(N)\) integers as bit masks.

Member Function Documentation

range_min()

template<typename T , typename Comp = std::less<T>>

T cplib::RangeMinQuery< T, Comp >::range_min ( size_type  left, size_type  right  ) const

inline

Returns the minimum element in the 0-based half-open range [left, right).

Returns \(\min\{a_{left},a_{left+1},\dots,a_{right-1}\}\). Time complexity is \(O(1)\) and specifically Comp is called at most 3 times.

Requires 0 <= left < right <= size(). Note that empty range is not allowed.

---

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

• src/cplib/range/rmq.hpp