sparse_table.cpp File Reference

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

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

Include dependency graph for sparse_table.cpp:

Go to the source code of this file.

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.

Implementation of Sparse Table data structure.

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.

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.

• Running Time Complexity
  
• Build : O(NlogN)
  
• Range Query : O(1)
  

Definition in file sparse_table.cpp.

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

Definition at line 162 of file sparse_table.cpp.

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

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

Definition at line 129 of file sparse_table.cpp.

                   {
    /* 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};  
    size_t testcase_size =
        sizeof(testcase) / sizeof(testcase[0]);  
 
    data_structures::sparse_table::Sparse_table
        st{};  
 
    std::copy(std::begin(testcase), std::end(testcase),
              std::begin(st.A));  
    st.n = testcase_size;         
 
    st.buildST();  
 
    // pass queries of the form: [l,r]
    assert(st.query(1, 9) == 1);  
    assert(st.query(2, 6) == 2);  
    assert(st.query(3, 8) == 3);  
 
    std::cout << "Self-test implementations passed!" << std::endl;
}

Variable Documentation

M

uint8_t data_structures::sparse_table::M = 14

constexpr

ceil(log2(N)).

Definition at line 49 of file sparse_table.cpp.

N

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.

Definition at line 48 of file sparse_table.cpp.