8#ifndef INCLUDED_SDSL_RMQ_SUPPORT_SPARSE_TABLE
9#define INCLUDED_SDSL_RMQ_SUPPORT_SPARSE_TABLE
20template <
class t_rac =
int_vector<>,
bool t_min = true>
21class rmq_support_sparse_table;
23template <
class t_rac =
int_vector<>>
42template <
class t_rac,
bool t_min>
47 std::vector<int_vector<>> m_table;
58 if (m_v ==
nullptr)
return;
63 while (2 * (1ULL << k) < n) ++k;
73 for (
size_type j = 0; j < m_table[i].size(); ++j)
76 (*m_v)[j + (1ULL << i) + m_table[i - 1][j + (1ULL << i)]])
79 << i) + m_table[i - 1]
112 if (l == r)
return l;
115 const size_type rr = r - (1ULL << k) + 1;
116 return mm_trait::compare((*m_v)[l + m_table[k - 1][l]], (*m_v)[rr + m_table[k - 1][rr]])
117 ? l + m_table[k - 1][l]
118 : rr + m_table[k - 1][rr];
139 return written_bytes;
142 void load(std::istream & in,
const t_rac * v)
153 template <
typename archive_t>
160 template <
typename archive_t>
int_vector_size_type size_type
A class to support range minimum or range maximum queries on a random access container.
rmq_support_sparse_table(const rmq_support_sparse_table &rm)=default
Copy constructor.
t_rac::size_type size_type
t_rac::size_type value_type
bool operator!=(rmq_support_sparse_table const &other) const noexcept
Inequality operator.
void load(std::istream &in, const t_rac *v)
rmq_support_sparse_table & operator=(rmq_support_sparse_table &&rm)=default
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
rmq_support_sparse_table & operator=(const rmq_support_sparse_table &rm)=default
rmq_support_sparse_table(const t_rac *v=nullptr)
bool operator==(rmq_support_sparse_table const &other) const noexcept
Equality operator.
size_type operator()(const size_type l, const size_type r) const
Range minimum/maximum query for the supported random access container v.
rmq_support_sparse_table(rmq_support_sparse_table &&rm)=default
Move constructor.
void set_vector(const t_rac *v)
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
rmq_support.hpp contains different range minimum support data structures.
static bool compare(const typename RandomAccessContainer::value_type v1, const typename RandomAccessContainer::value_type v2)
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.