sparse_table.cpp File Reference

Implementation of Sparse Table data structure. More...

#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>

Include dependency graph for sparse_table.cpp:

Namespaces
namespace	range_queries
	Algorithms and Data Structures that support range queries and updates.
namespace	sparse_table
	Functions for Implementation of Sparse Table

Functions
template<typename T >
std::vector< T >	range_queries::sparse_table::computeLogs (const std::vector< T > &A)
template<typename T >
std::vector< std::vector< T > >	range_queries::sparse_table::buildTable (const std::vector< T > &A, const std::vector< T > &logs)
template<typename T >
int	range_queries::sparse_table::getMinimum (int beg, int end, const std::vector< T > &logs, const std::vector< std::vector< T > > &table)
int	main ()

Detailed Description

Implementation of Sparse Table data structure.

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)
  

Function Documentation

buildTable()

template<typename T >

std::vector< std::vector< T > > range_queries::sparse_table::buildTable	(	const std::vector< T > &	A,
		const std::vector< T > &	logs
	)

This functions builds the primary data structure sparse table

Parameters

n	value of the size of the input array
A	array of the input integers
logs	array of the log table

Returns

created sparse table data structure

                                                                                     {
    int n = A.size();
    std::vector<std::vector<T> > table(20, std::vector<T>(n+5, 0));
    int curLen = 0;
    for (int i = 0 ; i <= logs[n] ; i++) {
        curLen = 1 << i;
        for (int j = 0 ; j + curLen < n ; j++) {
            if (curLen == 1) {
                table[i][j] = A[j];
            }
            else {
                table[i][j] = std::min(table[i-1][j], table[i-1][j + curLen/2]);
            }
        }
    }
    return table;
}

Here is the call graph for this function:

computeLogs()

template<typename T >

std::vector< T > range_queries::sparse_table::computeLogs

(

const std::vector< T > &

A

)

This function precomputes intial log table for further use.

Parameters

n	value of the size of the input array

Returns

corresponding vector of the log table

                                                {
    int n = A.size();
    std::vector<T> logs(n);
    logs[1] = 0;
    for (int i = 2 ; i < n ; i++) {
        logs[i] = logs[i/2] + 1;
    }
    return logs;
}

Here is the call graph for this function:

getMinimum()

template<typename T >

int range_queries::sparse_table::getMinimum	(	int	beg,
		int	end,
		const std::vector< T > &	logs,
		const std::vector< std::vector< T > > &	table
	)

This function is the query function to get the range minimum value

Parameters

beg	beginning index of the query range
end	ending index of the query range
logs	array of the log table
table	sparse table data structure for the input array

Returns

minimum value for the [beg, end] range for the input array

                                                                                                  {
    int p = logs[end - beg + 1];
    int pLen = 1 << p;
    return std::min(table[p][beg], table[p][end - pLen + 1]);
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function

           {
    std::vector<int> A{1, 2, 0, 3, 9};
    std::vector<int> logs = range_queries::sparse_table::computeLogs(A);
    std::vector<std::vector<int> >  table = range_queries::sparse_table::buildTable(A, logs);
    assert(range_queries::sparse_table::getMinimum(0, 0, logs, table) == 1);
    assert(range_queries::sparse_table::getMinimum(0, 4, logs, table) == 0);
    assert(range_queries::sparse_table::getMinimum(2, 4, logs, table) == 0);
    return 0;
}