Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d8/dab/sparse__table_8cpp_source.html below:

TheAlgorithms/C++: data_structures/sparse_table.cpp Source File

uint32_t

= 12345;

uint8_t

= 14;

std::array<int64_t, N>

= {};

std::array<std::array<int64_t, N>,

>

std::array<int64_t, N>

= {};

(

i = 0; i <

; ++i) {

[0][i] =

int64_t

(i);

[i + 1] =

[i] + !(i & (i + 1));

(

j = 1;

(1 << j) <=

; ++j) {

(

i = 0;

(i + (1 << j)) <=

; ++i) {

int64_t x =

[j - 1][i];

(

[x] <=

[y] ? x : y);

int64_t

(int64_t l, int64_t r) {

int64_t g =

[r - l + 1];

int64_t x =

[g][l];

[g][r - (1 << g) + 1];

(

[x] <=

[y] ? x : y);

std::array<int64_t, 10> testcase = {

testcase_size =

(testcase) /

(testcase[0]);

std::copy(std::begin(testcase), std::end(testcase),

st.

= testcase_size;

assert(st.

(1, 9) == 1);

assert(st.

(2, 6) == 2);

assert(st.

(3, 8) == 3);

std::cout <<

<< std::endl;

Functions for Implementation of Sparse Table

constexpr uint32_t N

A struct to represent sparse table for min() as their invariant function, for the given array A....

static void test()

Self-test implementations.

int main()

Main function.

constexpr uint8_t M

ceil(log2(N)).

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).

std::array< int64_t, N > LOG

where floor(log2(i)) are precomputed.

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.

size_t n

size of input array.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4