Sparse Table Algorithm
The Sparse Table Algorithm is a powerful technique used in computer science for efficiently processing range queries on static arrays. It is particularly useful for answering queries that involve associative functions, such as minimum, maximum, or greatest common divisor, with a preprocessing time complexity of O(n*log(n)) and a query time complexity of O(1). This algorithm is based on the concept of dynamic programming, leveraging the precomputed results and making use of the fact that the result of a function applied to a range of elements can be computed by combining the results of non-overlapping sub-ranges.
To construct a sparse table, the algorithm first initializes a 2D table, where the first dimension represents the array elements and the second dimension represents the range size as a power of two. The table is then filled with precomputed values in a bottom-up manner, using the dynamic programming principle. For each range size, the algorithm calculates the result of applying the function to the current range by combining the results of the previous smaller ranges. Once the sparse table is constructed, any query involving a range of elements can be answered efficiently by combining the precomputed values of the corresponding non-overlapping sub-ranges. This enables the algorithm to achieve constant time complexity for range queries on static arrays, making it a valuable tool in various applications such as data analysis, computational geometry, and graph theory.
/*************************************************************************************
Sparse table. Solves static RMQ problem (without element changes).
O(NlogN) on precalculation, O(1) on query.
Based on problem 3309 from informatics.mccme.ru:
http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3309
*************************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
using namespace std;
const int MAXN = 2 * 105000;
const int MAXLOG = 20;
int n, m;
int a[MAXN];
int table[MAXLOG][MAXN];
int numlog[MAXN];
void buildTable() {
numlog[1] = 0;
for (int i = 2; i <= n; i++)
numlog[i] = numlog[i / 2] + 1;
for (int i = 0; i <= numlog[n]; i++) {
int curlen = 1 << i;
for (int j = 1; j <= n; j++) {
if (i == 0) {
table[i][j] = a[j];
continue;
}
table[i][j] = max(table[i - 1][j], table[i - 1][j + curlen / 2]);
}
}
}
int getMax(int l, int r) {
int curlog = numlog[r - l + 1];
return max(table[curlog][l], table[curlog][r - (1 << curlog) + 1]);
}
int main() {
//assert(freopen("input.txt","r",stdin));
//assert(freopen("output.txt","w",stdout));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
buildTable();
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int l, r;
scanf("%d %d", &l, &r);
printf("%d ", getMax(l, r));
}
return 0;
}
