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

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 20 i.e 1.
This indicates that the least element in the array from any index in the range of size 1 ( 2 0 ) 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 22
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 = 20 (1)
Base case values
1
Length = 21 (2)
2
Length = 22 (4)
3
Length = 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 : 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
``````