RMQ Problem — Sparse Table Algorithm

This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

What is a Sparse Table?

A Sparse Table (ST Table) is an algorithm for solving range minimum/maximum query problems. It uses O(nlogn) preprocessing and can achieve O(1) query complexity. Drawback: Does not support online modifications. Template problem: Sparse Table - Luogu

1. Preprocessing

Use a 2D array dp[i][j] to represent the extreme value (maximum or minimum) from index i to i + 2^j - 1. Then: (1) The boundary condition is dp[i][0] = a[i], meaning the maximum from i to i is itself. (2) Next is the state transition equation, as shown in the figure:

1 << j is equivalent to 2^j

Initialization code:

void init(int n) {
    for (int i = 0; i < n; i++) {
        dp[i][0] = a[i];
    }
    for (int j = 1; (1<<j) <= n; j++) {
        for (int i = 0; i + (1<<j) <= n; i++) {
            dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
        }
    }
}

2. Query

Next is the query. Since the query interval length may not be exactly 2^j, we need the following theorem: (Reference: proof)

2^log(a) > a/2

log(a) represents the largest power of 2 that is less than or equal to a

e.g.: log(4)=2, log(5)=2, log(6)=2, log(7)=2, log(8)=3, log(9)=3

If we want to query the minimum value in the interval a to b: First compute the interval length len = b - a + 1 and let t = log(len). By the above theorem, 2^t > len/2, meaning 2^t extends into the right half of the interval [a, b]. The minimum of [a, b] is min(a to (a+2^t-1), (b-2^t+1) to b), as shown in the figure:

Query code:

ll sol(int a, int b) {
    int t = (int) (log(b-a+1.0)/log(2.0));
    return max(dp[a][t], dp[b-(1<<t)+1][t]);
}

3. Complete Code

Problem: Sparse Table - Luogu Needed O2 optimization and fast I/O to get AC.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 100000;
typedef long long ll;
ll a[maxn];
ll dp[maxn][25];//Using maximum as example here
void init(int n) {
    for (int i = 0; i < n; i++) {
        dp[i][0] = a[i];
    }
    for (int j = 1; (1<<j) <= n; j++) {
        for (int i = 0; i + (1<<j) <= n; i++) {
            dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
        }
    }
}
ll sol(int a, int b) {
    int t = (int) (log(b-a+1.0)/log(2.0));
    return max(dp[a][t], dp[b-(1<<t)+1][t]);
}
int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    init(n);
    while(m--) {
        int x,y;
        cin >> x >> y;
        cout << sol(x-1,y-1) << endl;
    }
    return 0;
}