data_structures::sparse_table::Sparse_table Struct Reference

Collaboration diagram for data_structures::sparse_table::Sparse_table:

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.

Member Function Documentation

query()

int64_t data_structures::sparse_table::Sparse_table::query ( int64_t l, int64_t r )

inline

Queries the sparse table for the value of the interval [l, r] (i.e. from l to r inclusive).

Parameters

l	the left index of the range (inclusive).
r	the right index of the range (inclusive).

Returns

the computed value of the given interval. @complexity: O(1)

< 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]

                                        {
        int64_t g = LOG[r - l + 1];  ///< smallest power of 2 covering [l,r]
        int64_t x = ST[g][l];  ///< represents minimum value over the range
                               ///< [g,l]
        int64_t y =
            ST[g][r - (1 << g) + 1];  ///< represents minimum value over the
                                      ///< range [g, r - pow(2,g) + 1]
 
        return (A[x] <= A[y] ? x : y);  ///< represents minimum value over
                                        ///< the whole range [l,r]
    }

Member Data Documentation

A

std::array<int64_t, N> data_structures::sparse_table::Sparse_table::A = {}

input array to perform RMQ.

Warning

check if N is not less than n. if so, manually increase the value of N

{};  ///< input array to perform RMQ.

LOG

std::array<int64_t, N> data_structures::sparse_table::Sparse_table::LOG = {}

where floor(log2(i)) are precomputed.

{};  ///< where floor(log2(i)) are precomputed.

ST

std::array<std::array<int64_t, N>, M> data_structures::sparse_table::Sparse_table::ST {}

the sparse table storing min() values for given interval.

{};  ///< the sparse table storing `min()` values for given interval.

---

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

• data_structures/sparse_table.cpp