Range Minimum/Maximum Query (RMQ)

The RMQ problem involves finding the minimum or maximum value within a specified range of an array of length n. Given multiple queries of the form RMQ(A, i, j), where i and j are indices in the array, the task is to return smallest or largest element between positions i and j.

Sparse Table Algorithm

The Sparse Table (ST) algorithm combines dynamic programming with a binary lifting technique. It is designed for static ranges and cannot handle updates efficiently; for dynamic scenarios, a segment tree would be more appropriate.

Basic Concept

We define f[i][j] as the maximum value in a subarray starting at index i and having a length of 2^j. For example, f[2][2] represents the maximum value among elements from a[2] through a[5]. When j = 0, f[i][0] simply corrseponds to a[i].

Binary Lifting Approach

To compute the maximum value in a range like a[l] to a[r], we can decompose it into two overlapping segments of power-of-two lengths. For instance, if we want to find the maximum in a[2] to a[14], we could split it into a[2] to a[9] and a[9] to a[14], then take the maximum of these two results.

Since j denotes 2^j, and we're using a divide-and-conquer strategy, logarithmic operations naturally emerge:

int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

Preprocessing Phase

Before querying, we must precompute all value in the table f[i][j] so that range queries can be answered quickly.

for (int j = 1; j <= 21; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
        f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }
}

Complete Implementation Template

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

const int N = 1e5 + 10;
int f[N][21];

inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
    int n, m;
    n = read();
    m = read();
    
    for (int i = 1; i <= n; ++i) {
        f[i][0] = read();
    }

    for (int j = 1; j <= 21; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }

    for (int i = 1; i <= m; ++i) {
        int l = read();
        int r = read();
        printf("%d\n", query(l, r));
    }

    return 0;
}