# Range Minimum Queries Using A Sparse Table

#### Doing range minimum queries using a sparse table.

Range Minimum Query (RMQ) finds the least element in an array between a range of indices.

The idea of this algorithm is to build a sparse table in a bottom-up manner using dynamic programming.

• The row numbers in the sparse table indicate the array indices.
• The column numbers indicate the range of size 2^(column) from the index. Using the sparse table reduces the query time to O ( 1 ).

Base case for building a sparse table
The base case values are filled in column 0 for every row. i.e For column 0 the range size is 2^0 i.e Just 1 number.
This indicates that the least element in the array from any index in the range of size 1 is the element itself.

Example of building a sparse table

• Sparse table [ 0 ] [ 1 ] represents the minimum array element from index 0 and range 2^1.
i.e 2 numbers from and including 0 are covered in this index range. i.e 0 till 1.
Thus table [ 0 ] [ 1 ] = minimum of ( table [ 0 ] [ 0 ] , table [ 1 ] [ 0 ] ).
• Sparse table [ 2 ] [ 2 ] represents the minimum array element from index 2 and range 2^2
i.e 4 numbers from and including 2 are covered in this index range. i.e 2 till 5.
Thus table [ 2 ] [ 2 ] = minimum of elements from ( 2 … 3 , 4 … 5 ) i.e minimum of ( table [ 2 ] [ 1 ] , table [ 4 ] [ 1 ] ).

Array :   4   6   8   7   3   2   9   5   1
Index :   0   1   2   3   4   5   6   7   8

Sparse table

Columns →

Rows
↓
0
Length = 2^0 (1)
Base case values
1
Length = 2^1 (2)
2
Length = 2^2 (4)
3
Length = 2^3 (8)
0 table [ 0 ] [ 0 ] = 4 table [ 0 ] [ 1 ] = 4
i.e min ( table [ 0 ] [ 0 ] , table [ 1 ] [ 0 ] )
i.e min ( Array [ 0 . . 1 ] )
table [ 0 ] [ 2 ] = 4
i.e min ( table [ 0 ] [ 1 ] , table [ 2 ] [ 1 ] )
i.e min ( Array [ 0 . . 3 ] )
table [ 0 ] [ 3 ] = 2
i.e min ( table [ 0 ] [ 2 ] , table[ 4 ] [ 2 ] )
i.e min ( Array [ 0 . . 7 ] )
1 table [ 1 ] [ 0 ] = 6 table [ 1 ] [ 1 ] = 6
i.e min ( table [ 1 ] [ 0 ] , table [ 2 ] [ 0 ] )
i.e min ( Array [ 1 . . 2 ] )
table [ 1 ] [ 2 ] = 3
i.e min ( table [ 1 ] [ 1 ] , table [ 3 ] [ 1 ] )
i.e min ( Array [ 1 . . 4 ] )
table [ 1 ] [ 3 ] = 1
i.e min ( table [ 1 ] [ 2 ] , table[ 5 ] [ 2 ] )
i.e min ( Array [ 1 . . 8 ] )
2 table [ 2 ] [ 0 ] = 8 table [ 2 ] [ 1 ] = 7
i.e min ( table [ 2 ] [ 0 ] , table [ 3 ] [ 0 ] )
i.e min ( Array [ 2 . . 3 ] )
table [ 2 ] [ 2 ] = 2
i.e min ( table [ 2 ] [ 1 ] , table [ 4 ] [ 1 ] )
i.e min ( Array [ 2 . . 5 ] )
3 table [ 3 ] [ 0 ] = 7 table [ 3 ] [ 1 ] = 3
i.e min ( table [ 3 ] [ 0 ] , table [ 4 ] [ 0 ] )
i.e min ( Array [ 3 . . 4 ] )
table [ 3 ] [ 2 ] = 2
i.e min ( table [ 3 ] [ 1 ] , table [ 5 ] [ 1 ] )
i.e min ( Array [ 3 . . 6 ] )
4 table [ 4 ] [ 0 ] = 3 table [ 4 ] [ 1 ] = 2
i.e min ( table [ 4 ] [ 0 ] , table [ 5 ] [ 0 ] )
i.e min ( Array [ 4 . . 5 ] )
table [ 4 ] [ 2 ] = 2
i.e min ( table [ 4 ] [ 1 ] , table [ 6 ] [ 1 ] )
i.e min ( Array [ 4 . . 7 ] )
5 table [ 5 ] [ 0 ] = 2 table [ 5 ] [ 1 ] = 2
i.e min ( table [ 5 ] [ 0 ] , table [ 6 ] [ 0 ] )
i.e min ( Array [ 5 . . 6 ] )
table [ 5 ] [ 2 ] = 1
i.e min ( table [ 5 ] [ 1 ] , table [ 7 ] [ 1 ] )
i.e min ( Array [ 5 . . 8 ] )
6 table [ 6 ] [ 0 ] = 9 table [ 6 ] [ 1 ] = 5
i.e min ( table [ 6 ] [ 0 ] , table [ 7 ] [ 0 ] )
i.e min ( Array [ 6 . . 7 ] )
7 table [ 7 ] [ 0 ] = 5 table [ 7 ] [ 1 ] = 1
i.e min ( table [ 7 ] [ 0 ] , table [ 8 ] [ 0 ] )
i.e min ( Array [ 7 . . 8 ] )
8 table [ 8 ] [ 0 ] = 1

Finding the minimum value in a given range
The trick is to find two sub-ranges within the query range such that they cover the entire range. If the range in the query is “left..right”, we choose the largest 2^p block that fits within left and right. Thus if 2^p is the largest block within ( left .. right ), then the first part is ( left .. left + 2^p - 1 ) and the second part is ( right + 1 - (2^p) .. right ).

Example of range minimum query
For i = 2 and j = 7. Within range 2 … 7, the largest 2^p block would be of size 2^2. Thus,
Part 1 : 2 … ( 2 + 2^2 - 1) i.e from 2 … 5. of length ( 5 + 1 - 2 ) : 4. This is represented by sparse table [ 2 ][ 2 ].
Part 2 : ( 7 + 1 - 2^2 ) … 7. i.e from 4 … 7 of length ( 7 + 1 - 2^2 ) : 4. This is represented by sparse table [ 4 ][ 2 ].
So the RMQ ( 2, 7 ) = minimum ( table [ 2 ][ 2 ] , table [ 4 ][ 2 ] ) = 2.

Time complexity of Range Minimum Queries using Sparse Table : O ( n . log (n) ). Sparse table has ‘n’ rows and ‘log n’ columns. The sparse table takes O ( n . log (n) ) time to fill up.

C++ : Range Minimum Queries implementation using Sparse Table in C++11

``````#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

void Print_SparseTable (vector<vector<int>>& sparse_table) {

int rows = sparse_table.size();
int cols = sparse_table[0].size();

cout << "Sparse table..." << endl;
cout << "---------------" << endl;
for (int r=0; r<rows; r++) {
for (int c=0; c<cols; c++) {
cout << sparse_table[r][c] << " ";
} cout << endl;
}
cout << "---------------" << endl;
}

void Build_SparseTable (vector<int>& vec, vector<vector<int>>& sparse_table) {

int rows = vec.size();
int cols = sparse_table[0].size();

for (int r=0; r<rows; r++)
sparse_table[r][0] = vec[r];

for (int c=1; c <= cols; c++) {
int range = (1 << c);
/* For  c    Range     c-1  Previous Range
1   2^1 = 2     0      2^0 = 1
2   2^2 = 4     1      2^1 = 2
3   2^3 = 8     2      2^2 = 4
...         */
for (int r=0; r + range <= rows; r++) {
// Values in the current column are derived from the
// values in the previous column.
sparse_table[r][c] = min (sparse_table[r][c-1],
sparse_table[r+(1<<(c-1))][c-1]);
}
}

Print_SparseTable(sparse_table);
}

int RMQ (int left, int right, vector<vector<int>>& sparse_table) {

// Find the biggest block of size 2^p that fits in the range "left" till "right".

int power_of_2 = (int) log2( right + 1 - left );
int x = right + 1 - ( 1 << power_of_2 );

cout << "Left : " << left << " Right : " << right << endl;
cout << "Part 1: (" << left << ".." << left + ( 1 << power_of_2 ) - 1 << ")" << " Part 2: (" << right + 1 - ( 1 << power_of_2 ) << ".." << right << ")" << endl;

if ( sparse_table[left][power_of_2] <= sparse_table[right + 1 - ( 1 << power_of_2 )][power_of_2] )
return sparse_table[left][power_of_2];
else
return sparse_table[right + 1 - ( 1 << power_of_2)][power_of_2];
}

int main()
{
vector<int> vec = { 4, 6, 8, 7, 3, 2, 9, 5, 1};

cout << "Index : ";
for (int i=0; i<vec.size(); i++) {
cout << i << " ";
} cout << endl;

cout << "Array : ";
for (auto& it : vec) {
cout << it << " ";
} cout << endl;

// Calculate the column size required for creating the sparse table
// Columns = log2 (number_count) + 1; log2(x) can also be calculated as log2(x) = log(x)/log(2) + 1
int sz = ceil (log2 (vec.size()) ) + 1;

// Create a sparse table of size [number_count][ceil ( log2 (number_count)) + 1]
vector<vector<int>> sparse_table (vec.size(), vector<int>(sz));

Build_SparseTable (vec, sparse_table);

cout << "Range Minium Queries (2, 7) : " <<  RMQ (2, 7, sparse_table) << endl << endl;
cout << "Range Minium Queries (0, 2) : " <<  RMQ (0, 2, sparse_table) << endl << endl;
cout << "Range Minium Queries (0, 8) : " <<  RMQ (0, 8, sparse_table) << endl << endl;
cout << "Range Minium Queries (4, 5) : " <<  RMQ (4, 5, sparse_table) << endl << endl;
cout << "Range Minium Queries (7, 8) : " <<  RMQ (7, 8, sparse_table) << endl << endl;
cout << "Range Minium Queries (1, 4) : " <<  RMQ (1, 4, sparse_table) << endl << endl;

return 0;
}
``````

Output

``````Index : 0 1 2 3 4 5 6 7 8
Array : 4 6 8 7 3 2 9 5 1
Sparse table...
---------------
4 4 4 2 0
6 6 3 1 0
8 7 2 0 0
7 3 2 0 0
3 2 2 0 0
2 2 1 0 0
9 5 0 0 0
5 1 0 0 0
1 0 0 0 0
---------------
( Left : 2, Right : 7 )
Part 1: (2..5) Part 2: (4..7)
Range Minium Queries (2, 7) : 2

( Left : 0, Right : 2 )
Part 1: (0..1) Part 2: (1..2)
Range Minium Queries (0, 2) : 4

( Left : 0, Right : 8 )
Part 1: (0..7) Part 2: (1..8)
Range Minium Queries (0, 8) : 1

( Left : 4, Right : 5 )
Part 1: (4..5) Part 2: (4..5)
Range Minium Queries (4, 5) : 2

( Left : 7, Right : 8 )
Part 1: (7..8) Part 2: (7..8)
Range Minium Queries (7, 8) : 1

( Left : 1, Right : 4 )
Part 1: (1..4) Part 2: (1..4)
Range Minium Queries (1, 4) : 3
``````