Sparse Table

Hey lads, today I will talk about Sparse Table (a Data Structure) which helps in solving range queries from static array (immutable arrays).

First, let's see a problem from cses.fi which can be solved using this DS.

Here we can see that there are n values and q query in which minimum value between range [a,b] is asked. here constraints are up to 2⋅10⁵. so, if we think about the brute force approach which will surely gonna give us a TLE verdict.

There are many data structure which we can be applied here but a sparse table is best because we can solve overlapping friendly function in O(1), and if it is not overlapping friendly then we can solve in O(logn). And, of course, the minimum function is an overlapping friendly function. So, we will be able to solve the query in O(1).

Sparse Table is easy to code and also, easy to remember.

For more details, I will refer to the cp-algorithms.com

The main idea behind the sparse table is to precompute the values for range queries with a power of two lengths. Since any number can be made from a power of 2, so any range can be answered from that table.

Pros:

• Easy to write and remember
• Can answer in O(1)

Cons:

• Not work in update query

Code 👇️

#include "bits/stdc++.h"
using namespace std;
using int64 = long long;
const char nwl = '\n';
const int mxx = 2e5 + 123;
int n, q, arr[mxx], dp[30][mxx];
void buildTable() {
 for (int i = 1; i <= n; i++) {
  dp[0][i] = arr[i];
 }
 int k = log2(n);
 for (int j = 1; j <= k; j++) {
  int p = 1 << (j - 1);
  for (int i = 1; i <= n; i++) {
   if (i + 2 * p - 1 > n) break;
   dp[j][i] = min(dp[j - 1][i], dp[j - 1][i + p]);
  }
 }
}
int ansQuery(int l, int r) {
 int c = log2(r - l + 1);
 return min(dp[c][l], dp[c][r + 1 - (1 << c)]);
}
int main() {
 cin >> n >> q;
 for (int i = 1; i <= n; i++) {
  cin >> arr[i];
 }
buildTable();
for (int i = 1; i <= q; i++) {
  int l, r;
  cin >> l >> r;
  cout << ansQuery(l, r) << nwl;
 }
return 0;
}