Range query data structures

Classes
class	cplib::BitDict
	Static bit sequence with rank query in \(O(1)\). More...
class	cplib::RangeMinQuery< T, Comp >
	Efficient \(\langle O(N), O(1) \rangle\) static range minimum query. More...
class	cplib::SparseTable< T, Op >
	\(\langle O(N\log N), O(1) \rangle\) sparse table for certain binary operations like min and gcd. More...
class	cplib::WaveletArray< T, M >
	Efficient representation of a wavelet tree, supporting various static range queries. More...

Functions
template<typename RandomIt , typename Range , std::enable_if_t< impl::is_static_query_range_v< Range, typename std::iterator_traits< RandomIt >::value_type > > * = nullptr>
std::vector< decltype(std::declval< Range >().get())>	cplib::batch_range_queries (Range &range, const std::vector< std::pair< RandomIt, RandomIt > > &queries)
	Batch range queries using Mo's algorithm.

Detailed Description

Function Documentation

batch_range_queries()

template<typename RandomIt , typename Range , std::enable_if_t< impl::is_static_query_range_v< Range, typename std::iterator_traits< RandomIt >::value_type > > * = nullptr>

std::vector< decltype(std::declval< Range >().get())> cplib::batch_range_queries	(	Range &	range,
		const std::vector< std::pair< RandomIt, RandomIt > > &	queries
	)

Batch range queries using Mo's algorithm.

Given a Range object that supports pushing and popping elements on both ends and querying some property about the range it currently holds, this functions answers \(Q\) range queries for that property given as subranges of a range of length \(N\), calling Range's push/pop methods \(O(N\sqrt{Q})\) times.

Template Parameters

Range

must have the following methods, where T is the value type of the queries' iterator type void Range::push_front(const T&) void Range::push_back(const T&) void Range::pop_front(const T&) void Range::pop_back(const T&) R Range::get()