sdsl::rmq_support_sparse_table< RandomAccessContainer, Minimum > Class Template Reference

A class to support range minimum or range maximum queries on a random access container. More...

#include <rmq_support_sparse_table.hpp>

List of all members.

Public Types
typedef RandomAccessContainer::size_type	size_type
typedef RandomAccessContainer::size_type	value_type
Public Member Functions
	rmq_support_sparse_table (const RandomAccessContainer *v=NULL)
	rmq_support_sparse_table (const rmq_support_sparse_table &rm)
	Copy constructor.
rmq_support_sparse_table &	operator= (const rmq_support_sparse_table &rm)
void	swap (rmq_support_sparse_table &rm)
void	set_vector (const RandomAccessContainer *v)
size_type	operator() (const size_type l, const size_type r) const
	Range minimum/maximum query for the supported random access container v.
size_type	size () const
size_type	serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const
void	load (std::istream &in, const RandomAccessContainer *v)

---

Detailed Description

template<class RandomAccessContainer, bool Minimum>
class sdsl::rmq_support_sparse_table< RandomAccessContainer, Minimum >

A class to support range minimum or range maximum queries on a random access container.

This class takes two template parameters. The first on is the type of random access container, for which the range minimum/maximum support should be build. The second one specifies whether the data structure should answer range minimum queries (Minimum=true) or range maximum queries (Maximum=false).

Time complexity

for the range minimum/maximum queries.

Space complexity:

bits for the data structure ( ). We used bit compression to get a good result in practice.

---

Member Function Documentation

template<class RandomAccessContainer , bool Minimum>

size_type sdsl::rmq_support_sparse_table< RandomAccessContainer, Minimum >::operator()	(	const size_type	l,
		const size_type	r
	)		const [inline]

Range minimum/maximum query for the supported random access container v.

Parameters:

l	Leftmost position of the interval .
r	Rightmost position of the interval .

Returns:

The minimal index i with for which is minimal/maximal.

Precondition:

• r < size()
• 

Time complexity

---

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

• sdsl/include/sdsl/rmq_support_sparse_table.hpp