Algotree > Algorithms > Range Minimum Queries Using A Sparse Table

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⁰ 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¹.
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²
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⁰ (1) Base case values	1 Length = 2¹ (2)	2 Length = 2² (4)	3 Length = 2³ (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

Range_Minimum_Query_Sparse_Table

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². Thus,
Part 1 : 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² ) … 7. i.e from 4 … 7 of length ( 7 + 1 - 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

#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