cplib::SparseTable< T, Op > Class Template Reference

\(\langle O(N\log N), O(1) \rangle\) sparse table for certain binary operations like min and gcd. More...

#include <sparse_table.hpp>

Public Types
using	size_type = std::size_t

Public Member Functions
	SparseTable ()=default
	Creates an empty sparse table.
	SparseTable (const std::vector< T > &data)
	Construct the sparse table from the given sequence.
	SparseTable (std::vector< T > &&data)
	Construct the sparse table from the given sequence.
template<typename InputIt >
	SparseTable (InputIt first, InputIt last)
	Construct the sparse table from the given sequence.
size_type	size () const
	Returns number of elements in the sequence.
T	range (size_type left, size_type right) const
	Iterated application of operator Op on elements in the 0-based half-open range [left, right).

Detailed Description

template<typename T, typename Op>
class cplib::SparseTable< T, Op >

\(\langle O(N\log N), O(1) \rangle\) sparse table for certain binary operations like min and gcd.

Template Parameters

T	T Type of elements.
Op	A function object that takes two T's and returns a T. Must be associative, commutative and idempotent.

Constructor & Destructor Documentation

SparseTable() [1/3]

template<typename T , typename Op >

cplib::SparseTable< T, Op >::SparseTable ( const std::vector< T > &  data )

inline

Construct the sparse table from the given sequence.

Makes \(O(N\log N)\) calls to Op and creates \(O(N\log N)\) copies of sequence elements.

SparseTable() [2/3]

template<typename T , typename Op >

cplib::SparseTable< T, Op >::SparseTable ( std::vector< T > &&  data )

inline

Construct the sparse table from the given sequence.

Makes \(O(N\log N)\) calls to Op and creates \(O(N\log N)\) copies of sequence elements.

SparseTable() [3/3]

template<typename T , typename Op >

template<typename InputIt >

cplib::SparseTable< T, Op >::SparseTable ( InputIt  first, InputIt  last  )

inline

Construct the sparse table from the given sequence.

Makes \(O(N\log N)\) calls to Op and creates \(O(N\log N)\) copies of sequence elements.

Member Function Documentation

range()

template<typename T , typename Op >

T cplib::SparseTable< T, Op >::range ( size_type  left, size_type  right  ) const

inline

Iterated application of operator Op on elements in the 0-based half-open range [left, right).

If \(\circ\) denotes Op, this returns \(a_{left} \cdots a_{left+1} \circ \dots \circ a_{right-1}\). Time complexity is \(O(1)\) and specfically Op is called at most once.

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/sparse_table.hpp