Range Minimum Query (RMQ)

¿Qué es RMQ?

Analogía: Imagina que tienes una fila de montañas y un turista te pregunta: "¿Cuál es la montaña más baja entre la posición 3 y la posición 8?". Si te hacen esta pregunta miles de veces con diferentes rangos, necesitas una forma rápida de responder. Eso es Range Minimum Query (consulta del mínimo en un rango).

Dado un arreglo, responder consultas: ¿cuál es el mínimo en el rango [l, r]?

Solución ingenua: $O(n)$ por consulta

int queryMin(vector<int> &v, int l, int r) {
    int mn = v[l];
    for (int i = l + 1; i <= r; i++) {
        mn = min(mn, v[i]);
    }
    return mn;
}

Con Q consultas → $O(n \cdot Q)$. Demasiado lento.

Sparse Table: $O(n \log n)$ preproceso, $O(1)$ por consulta

Idea: Precalcular el mínimo de todos los bloques de tamaño potencia de 2.

sparse[k][i] = mínimo del rango que empieza en i y tiene longitud $2^k$.

sparse[0][i] = v[i]             (bloques de tamaño 1)
sparse[1][i] = min(v[i], v[i+1])  (bloques de tamaño 2)
sparse[2][i] = min de v[i..i+3]   (bloques de tamaño 4)
...

Construcción

const int MAXN = 200005;
const int LOG = 18;

int sparse[LOG][MAXN];
int n;

void build(vector<int> &v) {
    n = v.size();

    // Bloques de tamaño 1
    for (int i = 0; i < n; i++) {
        sparse[0][i] = v[i];
    }

    // Bloques de tamaño 2^k
    for (int k = 1; k < LOG; k++) {
        for (int i = 0; i + (1 << k) - 1 < n; i++) {
            sparse[k][i] = min(
                sparse[k-1][i],                  // Primera mitad
                sparse[k-1][i + (1 << (k-1))]    // Segunda mitad
            );
        }
    }
}

¿Por qué funciona? Un bloque de tamaño $2^k$ se divide en dos bloques de tamaño $2^{k-1}$:

[-------- 2^k --------]
[--- 2^(k-1) ---][--- 2^(k-1) ---]

Consulta en $O(1)$

Para un rango [l, r], encontramos la mayor potencia de 2 que cabe, y usamos dos bloques que cubran todo el rango (pueden traslaparse, ¡no importa para el mínimo!):

int query(int l, int r) {
    int len = r - l + 1;
    int k = __lg(len);  // floor(log2(len))

    return min(
        sparse[k][l],                  // Bloque desde l
        sparse[k][r - (1 << k) + 1]   // Bloque hasta r
    );
}

Rango [2, 9] con k = 3 (2^3 = 8):
[2 3 4 5 6 7 8 9]
[2 3 4 5 6 7 8 9]  ← bloque desde l=2
    [2 3 4 5 6 7 8 9] ← bloque hasta r=9
Se traslapan, pero min(min_A, min_B) = min total ✓

Código completo

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 200005;
const int LOG = 18;
int sparse[LOG][MAXN];

void build(vector<int> &v, int n) {
    for (int i = 0; i < n; i++)
        sparse[0][i] = v[i];

    for (int k = 1; k < LOG; k++)
        for (int i = 0; i + (1 << k) - 1 < n; i++)
            sparse[k][i] = min(sparse[k-1][i],
                               sparse[k-1][i + (1 << (k-1))]);
}

int query(int l, int r) {
    int k = __lg(r - l + 1);
    return min(sparse[k][l], sparse[k][r - (1 << k) + 1]);
}

int main() {
    int n, q;
    cin >> n >> q;

    vector<int> v(n);
    for (int &x : v) cin >> x;

    build(v, n);

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--; r--;  // 0-indexed
        cout << query(l, r) << "\n";
    }

    return 0;
}

¿Cuándo usar Sparse Table vs Segment Tree?

Regla: Si el arreglo no cambia, usa Sparse Table. Si hay actualizaciones, usa Segment Tree.

Ejercicio

Dado un arreglo de N enteros y Q consultas (l, r), imprime el máximo de cada rango.

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 200005;
const int LOG = 18;
int sparse[LOG][MAXN];

void build(vector<int> &v, int n) {
    for (int i = 0; i < n; i++)
        sparse[0][i] = v[i];

    for (int k = 1; k < LOG; k++)
        for (int i = 0; i + (1 << k) - 1 < n; i++)
            sparse[k][i] = max(sparse[k-1][i],
                               sparse[k-1][i + (1 << (k-1))]);
}

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (int &x : v) cin >> x;
    build(v, n);

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        cout << query(l, r) << "\n";
    }
    return 0;
}