sdsl::rmq_succinct_sct< Minimum, Bp_support > Class Template Reference

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

#include <rmq_succinct_sct.hpp>

List of all members.

Public Types
typedef bit_vector::size_type	size_type
typedef bit_vector::size_type	value_type
Public Member Functions
	rmq_succinct_sct ()
	Default constructor.
template<class RandomAccessContainer >
	rmq_succinct_sct (const RandomAccessContainer *v=NULL)
	Constructor.
	rmq_succinct_sct (const rmq_succinct_sct &rm)
	Copy constructor.
	~rmq_succinct_sct ()
	Destructor.
rmq_succinct_sct &	operator= (const rmq_succinct_sct &rm)
void	swap (const rmq_succinct_sct &rm)
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)
Public Attributes
const bit_vector &	sct_bp
const Bp_support &	sct_bp_support

---

Detailed Description

template<bool Minimum, class Bp_support>
class sdsl::rmq_succinct_sct< Minimum, Bp_support >

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

This class takes three template parameters:

• minumum specifies whether the data structure should answer range minimum queries (mimumum=true) of range maximum queries (maximum=false), and
• Bp_support is the support structure for the balanced parentheses sequence of the Super-Cartesian tree used internal in the class.

  Time complexity

  for the range minimum/maximum queries if the balanced parentheses support structure supports constant time operations.

  Space complexity:

  bits for the data structure ( ).

---

Member Function Documentation

template<bool Minimum, class Bp_support >

size_type sdsl::rmq_succinct_sct< Minimum, Bp_support >::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_succinct_sct.hpp