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.

Detailed Description

Definition at line 51 of file sparse_table.cpp.

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]

Definition at line 110 of file sparse_table.cpp.

                                        {
        int64_t g = LOG[r - l + 1];  
        int64_t x = ST[g][l];  
        int64_t y =
            ST[g][r - (1 << g) + 1];  
 
        return (A[x] <= A[y] ? x : y);  
    }

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

Definition at line 57 of file sparse_table.cpp.

{};  

LOG

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

where floor(log2(i)) are precomputed.

Definition at line 60 of file sparse_table.cpp.

{};  

n

size_t data_structures::sparse_table::Sparse_table::n = 0

size of input array.

Definition at line 52 of file sparse_table.cpp.

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.

Definition at line 59 of file sparse_table.cpp.

{};  

---

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

• data_structures/sparse_table.cpp