Algotree > Algorithms > Range Minimum Queries Using A Sparse Table

Range Minimum Queries Using A Sparse Table

Sparse Table

Sparse Table is a ( pre-computed ) data structure that is used for answering Range Minimum Queries ( RMQ ) on immutable arrays.
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 the range minimum query time taken is O ( 1 ).

As the Spare Table is pre-computed ( from an array ), it can only be used for an array that is immutable. i.e The array cannot be modified between queries. If case of any modifications to the array, the Sparse Table has to be recomputed.

Range Minimum Query (RMQ)

RMQ finds the smallest element in an array between a range of indices.

Building a Sparse Table

A sparse table can be built 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.
As the column numbers indicate the range of size 2 ^{( column )} from the index, for column 0 the range size is 2⁰ i.e 1.
This indicates that the least element in the array from any index in the range of size 1 ( 2 ⁰ ) 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 : 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.

Program for doing range minimum queries (RMQ) using Sparse Table

from typing import List
import math

def Build_SparseTable (array : List[int], sparse_table : List[List[int]]) :

    rows = len(array)
    cols = len(sparse_table[0])

    # Fill base case values
    for r in range(rows) :
        sparse_table[r][0] = array[r]

    for c in range(1, cols+1) :
        _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
        #        ...
        r = 0
        while (r + _range <= rows) :
            # 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])
            r += 1

    print("Sparse Table")
    for row in (sparse_table):
        print(row)

def RMQ (left : int, right : int, sparse_table : List[List[int]]) :

    # Find the biggest block of size 2^p that fits in the range (left) ... (right).

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

    print ("Left : " + str(left) + " Right : " + str(right))
    print ("Part 1: ( " + str(left) + "..." + str(left + ( 1 << power_of_2 ) - 1) + " ) " + \
           "Part 2: ( " + str(right + 1 - ( 1 << power_of_2 )) + "..." + str(right) + " )")

    if (sparse_table[left][power_of_2] <= sparse_table[right + 1 - ( 1 << power_of_2 )][power_of_2]) :
        print ("Smallest number : " + str(sparse_table[left][power_of_2]))
    else :
        print ("Smallest number : " + str(sparse_table[right + 1 - ( 1 << power_of_2)][power_of_2]))

def main() :

    array = [ 4, 6, 8, 7, 3, 2, 9, 5, 1 ]

    print ("Index : ", end = ' ')
    for i in range(len(array)) :
        print (str(i) + " ", end=' ')

    print ("\nArray : " + str(array))

    # Calculate the column size required for creating the sparse table
    # Columns = log2 (number_count) + 1
    sz = math.ceil (math.log2 (len(array)) ) + 1

    # Create a sparse table of size [number_count][ceil ( log2 (number_count)) + 1]
    sparse_table = [0] * len(array)
    for i in range(len(array)) :
        sparse_table[i] = [0] * sz

    Build_SparseTable (array, sparse_table)

    print ("\nRange Minium Queries (2, 7) : ")
    RMQ (2, 7, sparse_table)
    print ("\nRange Minium Queries (0, 2) : ")
    RMQ (0, 2, sparse_table)
    print ("\nRange Minium Queries (0, 8) : ")
    RMQ (0, 8, sparse_table)
    print ("\nRange Minium Queries (4, 5) : ")
    RMQ (4, 5, sparse_table)
    print ("\nRange Minium Queries (7, 8) : ")
    RMQ (7, 8, sparse_table)
    print ("\nRange Minium Queries (1, 4) : ")
    RMQ (1, 4, sparse_table)

if __name__ == "__main__" :
    main()

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]

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

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

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

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

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

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

#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();

    // Fill base case values
    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);
}

void 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] )
        cout << "Smallest number : " << sparse_table[left][power_of_2] << endl;
    else
        cout << "Smallest number : " << sparse_table[right + 1 - ( 1 << power_of_2)][power_of_2] << endl;
}

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
    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);
    cout << endl;
    cout << "Range Minium Queries (0, 2) : " ; RMQ (0, 2, sparse_table);
    cout << endl;
    cout << "Range Minium Queries (0, 8) : " ; RMQ (0, 8, sparse_table);
    cout << endl;
    cout << "Range Minium Queries (4, 5) : " ; RMQ (4, 5, sparse_table);
    cout << endl;
    cout << "Range Minium Queries (7, 8) : " ; RMQ (7, 8, sparse_table);
    cout << endl;
    cout << "Range Minium Queries (1, 4) : " ; RMQ (1, 4, sparse_table);

    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 
---------------
Range Minium Queries (2, 7) : Left : 2 Right : 7
Part 1: ( 2...5 ) Part 2: ( 4...7 )
Smallest number : 2

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

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

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

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

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