Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Public Member Functions | |
int64_t | query (int64_t l, int64_t r) |
Queries the sparse table for the value of the interval [l, r] (i.e. from l to r inclusive). | |
Public Attributes | |
size_t | n = 0 |
size of input array. | |
std::array< int64_t, N > | A = {} |
input array to perform RMQ. | |
std::array< std::array< int64_t, N >, M > | ST {} |
the sparse table storing min() values for given interval. | |
std::array< int64_t, N > | LOG = {} |
where floor(log2(i)) are precomputed. | |
|
inline |
Queries the sparse table for the value of the interval [l, r] (i.e. from l to r inclusive).
l | the left index of the range (inclusive). |
r | the right index of the range (inclusive). |
< smallest power of 2 covering [l,r]
< represents minimum value over the range [g,l]
< represents minimum value over the range [g, r - pow(2,g) + 1]
< represents minimum value over the whole range [l,r]
std::array<int64_t, N> data_structures::sparse_table::Sparse_table::A = {} |
input array to perform RMQ.
N
is not less than n
. if so, manually increase the value of N std::array<int64_t, N> data_structures::sparse_table::Sparse_table::LOG = {} |
where floor(log2(i)) are precomputed.
std::array<std::array<int64_t, N>, M> data_structures::sparse_table::Sparse_table::ST {} |
the sparse table storing min()
values for given interval.