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