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 20 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 21.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 22i.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 ↓ | 0Length = 20 (1) Base case values | 1Length = 21 (2) | 2Length = 22 (4) | 3Length = 23 (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 2p block that fits within left and right. Thus if 2p is the largest block within ( left .. right ), then the first part is ( left .. left + 2p - 1 ) and the second part is ( right + 1 - (2p) .. right ). Example of range minimum query For i = 2 and j = 7. Within range 2 … 7, the largest 2p block would be of size 22. Thus, Part 1 : 2 … ( 2 + 22 - 1) i.e from 2 … 5. of length ( 5 + 1 - 2 ) : 4. This is represented by sparse table [ 2 ][ 2 ]. Part 2 : ( 7 + 1 - 22 ) … 7. i.e from 4 … 7 of length ( 7 + 1 - 22 ) : 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