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.
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
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