# Sparse Table

We have briefly discussed sparse table in Range Minimum Query (Square Root Decomposition and Sparse Table)

Sparse table concept is used for fast queries on a set of static data (elements do not change). It does preprocessing so that the queries can be answered efficiently.

Example Problem 1 : Range Minimum Query

We have an array arr[0 . . . n-1]. We need to efficiently find the minimum value from index L (query start) to R (query end) where 0 <= L <= R <= n-1. Consider a situation when there are many range queries.

Example:

```Input:  arr[]   = {7, 2, 3, 0, 5, 10, 3, 12, 18};
query[] = [0, 4], [4, 7], [7, 8]

Output: Minimum of [0, 4] is 0
Minimum of [4, 7] is 3
Minimum of [7, 8] is 12
```

The idea is to precompute minimum of all subarrays of size 2j where j varies from 0 to Log n. We make a table lookup[i][j] such that lookup[i][j] contains minimum of range starting from i and of size 2j. For example lookup[0][3] contains minimum of range [0, 7] (starting with 0 and of size 23)

How to fill this lookup or sparse table?
The idea is simple, fill in a bottom-up manner using previously computed values. We compute ranges with current power of 2 using values of lower power of two. For example, to find a minimum of range [0, 7] (Range size is a power of 3), we can use the minimum of following two.
a) Minimum of range [0, 3] (Range size is a power of 2)
b) Minimum of range [4, 7] (Range size is a power of 2)

Based on above example, below is formula,

```// Minimum of single element subarrays is same
// as the only element.
lookup[i][0] = arr[i]

// If lookup[0][2] <=  lookup[4][2],
// then lookup[0][3] = lookup[0][2]
If lookup[i][j-1] <= lookup[i+2j-1-1][j-1]
lookup[i][j] = lookup[i][j-1]

// If lookup[0][2] >  lookup[4][2],
// then lookup[0][3] = lookup[4][2]
Else
lookup[i][j] = lookup[i+2j-1-1][j-1] ```

For any arbitrary range [l, R], we need to use ranges which are in powers of 2. The idea is to use the closest power of 2. We always need to do at most one comparison (compare the minimum of two ranges which are powers of 2). One range starts with L and ends with “L + closest-power-of-2”. The other range ends at R and starts with “R – same-closest-power-of-2 + 1”. For example, if the given range is (2, 10), we compare the minimum of two ranges (2, 9) and (3, 10).

Based on above example, below is formula,

```// For (2, 10), j = floor(Log2(10-2+1)) = 3
j = floor(Log(R-L+1))

// If lookup[0][3] <=  lookup[3][3],
// then min(2, 10) = lookup[0][3]
If lookup[L][j] <= lookup[R-(int)pow(2, j)+1][j]
min(L, R) = lookup[L][j]

// If lookup[0][3] >  arr[lookup[3][3],
// then min(2, 10) = lookup[3][3]
Else
min(L, R) = lookup[i+2j-1-1][j-1]```

Since we do only one comparison, the time complexity of query is O(1).

Below is the implementation of the above idea.

## C++

 `// C++ program to do range minimum query ` `// using sparse table ` `#include ` `using` `namespace` `std; ` `#define MAX 500 ` ` `  `// lookup[i][j] is going to store minimum ` `// value in arr[i..j]. Ideally lookup table ` `// size should not be fixed and should be ` `// determined using n Log n. It is kept ` `// constant to keep code simple. ` `int` `lookup[MAX][MAX]; ` ` `  `// Fills lookup array lookup[][] in bottom up manner. ` `void` `buildSparseTable(``int` `arr[], ``int` `n) ` `{ ` `    ``// Initialize M for the intervals with length 1 ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``lookup[i][0] = arr[i]; ` ` `  `    ``// Compute values from smaller to bigger intervals ` `    ``for` `(``int` `j = 1; (1 << j) <= n; j++) { ` ` `  `        ``// Compute minimum value for all intervals with ` `        ``// size 2^j ` `        ``for` `(``int` `i = 0; (i + (1 << j) - 1) < n; i++) { ` ` `  `            ``// For arr[2][10], we compare arr[lookup[0][7]]  ` `            ``// and arr[lookup[3][10]] ` `            ``if` `(lookup[i][j - 1] <  ` `                        ``lookup[i + (1 << (j - 1))][j - 1]) ` `                ``lookup[i][j] = lookup[i][j - 1]; ` `            ``else` `                ``lookup[i][j] =  ` `                         ``lookup[i + (1 << (j - 1))][j - 1]; ` `        ``} ` `    ``} ` `} ` ` `  `// Returns minimum of arr[L..R] ` `int` `query(``int` `L, ``int` `R) ` `{ ` `    ``// Find highest power of 2 that is smaller ` `    ``// than or equal to count of elements in given ` `    ``// range. For [2, 10], j = 3 ` `    ``int` `j = (``int``)log2(R - L + 1); ` ` `  `    ``// Compute minimum of last 2^j elements with first ` `    ``// 2^j elements in range. ` `    ``// For [2, 10], we compare arr[lookup[0][3]] and ` `    ``// arr[lookup[3][3]], ` `    ``if` `(lookup[L][j] <= lookup[R - (1 << j) + 1][j]) ` `        ``return` `lookup[L][j]; ` ` `  `    ``else` `        ``return` `lookup[R - (1 << j) + 1][j]; ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``int` `a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 }; ` `    ``int` `n = ``sizeof``(a) / ``sizeof``(a[0]); ` `    ``buildSparseTable(a, n); ` `    ``cout << query(0, 4) << endl; ` `    ``cout << query(4, 7) << endl; ` `    ``cout << query(7, 8) << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java program to do range minimum query ` `// using sparse table ` `import` `java.io.*; ` ` `  `class` `GFG { ` ` `  `    ``static` `int` `MAX =``500``; ` `     `  `    ``// lookup[i][j] is going to store minimum ` `    ``// value in arr[i..j]. Ideally lookup table ` `    ``// size should not be fixed and should be ` `    ``// determined using n Log n. It is kept ` `    ``// constant to keep code simple. ` `    ``static` `int` `[][]lookup = ``new` `int``[MAX][MAX]; ` `     `  `    ``// Fills lookup array lookup[][] in bottom up manner. ` `    ``static` `void` `buildSparseTable(``int` `arr[], ``int` `n) ` `    ``{ ` `         `  `        ``// Initialize M for the intervals with length 1 ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``lookup[i][``0``] = arr[i]; ` `     `  `        ``// Compute values from smaller to bigger intervals ` `        ``for` `(``int` `j = ``1``; (``1` `<< j) <= n; j++) { ` `     `  `            ``// Compute minimum value for all intervals with ` `            ``// size 2^j ` `            ``for` `(``int` `i = ``0``; (i + (``1` `<< j) - ``1``) < n; i++) { ` `     `  `                ``// For arr[2][10], we compare arr[lookup[0][7]]  ` `                ``// and arr[lookup[3][10]] ` `                ``if` `(lookup[i][j - ``1``] <  ` `                            ``lookup[i + (``1` `<< (j - ``1``))][j - ``1``]) ` `                    ``lookup[i][j] = lookup[i][j - ``1``]; ` `                ``else` `                    ``lookup[i][j] =  ` `                            ``lookup[i + (``1` `<< (j - ``1``))][j - ``1``]; ` `            ``} ` `        ``} ` `    ``} ` `     `  `    ``// Returns minimum of arr[L..R] ` `    ``static` `int` `query(``int` `L, ``int` `R) ` `    ``{ ` `         `  `        ``// Find highest power of 2 that is smaller ` `        ``// than or equal to count of elements in given ` `        ``// range. For [2, 10], j = 3 ` `        ``int` `j = (``int``)Math.log(R - L + ``1``); ` `     `  `        ``// Compute minimum of last 2^j elements with first ` `        ``// 2^j elements in range. ` `        ``// For [2, 10], we compare arr[lookup[0][3]] and ` `        ``// arr[lookup[3][3]], ` `        ``if` `(lookup[L][j] <= lookup[R - (``1` `<< j) + ``1``][j]) ` `            ``return` `lookup[L][j]; ` `     `  `        ``else` `            ``return` `lookup[R - (``1` `<< j) + ``1``][j]; ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `main (String[] args) ` `    ``{ ` `        ``int` `a[] = { ``7``, ``2``, ``3``, ``0``, ``5``, ``10``, ``3``, ``12``, ``18` `}; ` `        ``int` `n = a.length; ` `         `  `        ``buildSparseTable(a, n); ` `         `  `        ``System.out.println(query(``0``, ``4``)); ` `        ``System.out.println(query(``4``, ``7``)); ` `        ``System.out.println(query(``7``, ``8``)); ` `     `  `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## Python3

# Python3 program to do range minimum
# query using sparse table
import math

# Fills lookup array lookup[][] in
# bottom up manner.
def buildSparseTable(arr, n):

# Initialize M for the intervals
# with length 1
for i in range(0, n):
lookup[i][0] = arr[i]

j = 1

# Compute values from smaller to
# bigger intervals
while (1 << j) <= n: # Compute minimum value for all # intervals with size 2^j i = 0 while (i + (1 << j) - 1) < n: # For arr[2][10], we compare arr[lookup[0][7]] # and arr[lookup[3][10]] if (lookup[i][j - 1] < lookup[i + (1 << (j - 1))][j - 1]): lookup[i][j] = lookup[i][j - 1] else: lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1] i += 1 j += 1 # Returns minimum of arr[L..R] def query(L, R): # Find highest power of 2 that is smaller # than or equal to count of elements in # given range. For [2, 10], j = 3 j = int(math.log2(R - L + 1)) # Compute minimum of last 2^j elements # with first 2^j elements in range. # For [2, 10], we compare arr[lookup[0][3]] # and arr[lookup[3][3]], if lookup[L][j] <= lookup[R - (1 << j) + 1][j]: return lookup[L][j] else: return lookup[R - (1 << j) + 1][j] # Driver Code if __name__ == "__main__": a = [7, 2, 3, 0, 5, 10, 3, 12, 18] n = len(a) MAX = 500 # lookup[i][j] is going to store minimum # value in arr[i..j]. Ideally lookup table # size should not be fixed and should be # determined using n Log n. It is kept # constant to keep code simple. lookup = [[0 for i in range(MAX)] for j in range(MAX)] buildSparseTable(a, n) print(query(0, 4)) print(query(4, 7)) print(query(7, 8)) # This code is contributed by Rituraj Jain [tabby title="C#"]

 `// C# program to do range minimum query ` `// using sparse table ` `using` `System; ` ` `  `public` `class` `GFG { ` `     `  `    ``static` `int` `MAX= 500; ` `     `  `    ``// lookup[i][j] is going to store minimum ` `    ``// value in arr[i..j]. Ideally lookup table ` `    ``// size should not be fixed and should be ` `    ``// determined using n Log n. It is kept ` `    ``// constant to keep code simple. ` `    ``static` `int` `[,]lookup = ``new` `int``[MAX, MAX]; ` `     `  `    ``// Fills lookup array lookup[][] in bottom up manner. ` `    ``static` `void` `buildSparseTable(``int` `[]arr, ``int` `n) ` `    ``{ ` `        ``// Initialize M for the intervals with length 1 ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``lookup[i, 0] = arr[i]; ` `     `  `        ``// Compute values from smaller to bigger intervals ` `        ``for` `(``int` `j = 1; (1 << j) <= n; j++) { ` `     `  `            ``// Compute minimum value for all intervals with ` `            ``// size 2^j ` `            ``for` `(``int` `i = 0; (i + (1 << j) - 1) < n; i++) { ` `     `  `                ``// For arr[2][10], we compare arr[lookup[0][7]]  ` `                ``// and arr[lookup[3][10]] ` `                ``if` `(lookup[i, j - 1] <  ` `                            ``lookup[i + (1 << (j - 1)), j - 1]) ` `                    ``lookup[i, j] = lookup[i, j - 1]; ` `                ``else` `                    ``lookup[i, j] =  ` `                            ``lookup[i + (1 << (j - 1)), j - 1]; ` `            ``} ` `        ``} ` `    ``} ` `     `  `    ``// Returns minimum of arr[L..R] ` `    ``static` `int` `query(``int` `L, ``int` `R) ` `    ``{ ` `         `  `        ``// Find highest power of 2 that is smaller ` `        ``// than or equal to count of elements in given ` `        ``// range. For [2, 10], j = 3 ` `        ``int` `j = (``int``)Math.Log(R - L + 1); ` `     `  `        ``// Compute minimum of last 2^j elements with first ` `        ``// 2^j elements in range. ` `        ``// For [2, 10], we compare arr[lookup[0][3]] and ` `        ``// arr[lookup[3][3]], ` `        ``if` `(lookup[L, j] <= lookup[R - (1 << j) + 1, j]) ` `            ``return` `lookup[L, j]; ` `     `  `        ``else` `            ``return` `lookup[R - (1 << j) + 1, j]; ` `    ``} ` `     `  `    ``// Driver program ` `    ``static` `public` `void` `Main () ` `    ``{ ` `        ``int` `[]a = { 7, 2, 3, 0, 5, 10, 3, 12, 18 }; ` `        ``int` `n = a.Length; ` `         `  `        ``buildSparseTable(a, n); ` `         `  `        ``Console.WriteLine(query(0, 4)); ` `        ``Console.WriteLine(query(4, 7)); ` `        ``Console.WriteLine(query(7, 8)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m.  `