sparse_table.cpp File Reference

Implementation of Sparse Table for min() function. More...

#include <array>
#include <cassert>
#include <iostream>

Include dependency graph for sparse_table.cpp:

Classes
struct	data_structures::sparse_table::Sparse_table

Namespaces
namespace	data_structures
	for IO operations
namespace	sparse_table
	Functions for Implementation of Sparse Table

Functions
static void	test ()
	Self-test implementations.
int	main (int argc, char *argv[])
	Main function.

Variables
constexpr uint32_t	data_structures::sparse_table::N = 12345
	A struct to represent sparse table for min() as their invariant function, for the given array A. The answer to queries are stored in the array ST.
constexpr uint8_t	data_structures::sparse_table::M = 14
	ceil(log2(N)).

Detailed Description

Implementation of Sparse Table for min() function.

Author

Mann Patel

Sparse Table is a data structure, that allows answering range queries. It can answer most range queries in O(logn), but its true power is answering range minimum queries (or equivalent range maximum queries). For those queries it can compute the answer in O(1) time. The only drawback of this data structure is, that it can only be used on immutable arrays. This means, that the array cannot be changed between two queries.

If any element in the array changes, the complete data structure has to be recomputed.

Todo

make stress tests.

Warning

This sparse table is made for min(a1,a2,...an) duplicate invariant function. This implementation can be changed to other functions like gcd(), lcm(), and max() by changing a few lines of code.

Function Documentation

main()

int main	(	int	argc,
		char *	argv[] )

Main function.

Parameters

argc	commandline argument count (ignored)
argv	commandline array of arguments (ignored)

Returns

0 on exit

                                 {
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

< array on which RMQ will be performed.

< size of self test's array

< declaring sparse tree

< copying array to the struct

< passing the array's size to the struct

< precomputing sparse tree

< as 1 is smallest from 1..9

< as 2 is smallest from 2..6

< as 3 is smallest from 3..8

                   {
    /* We take an array as an input on which we need to perform the ranged
     * minimum queries[RMQ](https://en.wikipedia.org/wiki/Range_minimum_query).
     */
    std::array<int64_t, 10> testcase = {
        1, 2, 3, 4, 5,
        6, 7, 8, 9, 10};  ///< array on which RMQ will be performed.
    size_t testcase_size =
        sizeof(testcase) / sizeof(testcase[0]);  ///< size of self test's array
 
    data_structures::sparse_table::Sparse_table
        st{};  ///< declaring sparse tree
 
    std::copy(std::begin(testcase), std::end(testcase),
              std::begin(st.A));  ///< copying array to the struct
    st.n = testcase_size;         ///< passing the array's size to the struct
 
    st.buildST();  ///< precomputing sparse tree
 
    // pass queries of the form: [l,r]
    assert(st.query(1, 9) == 1);  ///< as 1 is smallest from 1..9
    assert(st.query(2, 6) == 2);  ///< as 2 is smallest from 2..6
    assert(st.query(3, 8) == 3);  ///< as 3 is smallest from 3..8
 
    std::cout << "Self-test implementations passed!" << std::endl;
}

Here is the call graph for this function:

Variable Documentation

N

constexpr uint32_t data_structures::sparse_table::N = 12345

constexpr

A struct to represent sparse table for min() as their invariant function, for the given array A. The answer to queries are stored in the array ST.

the maximum size of the array.