🧱 Sparse table (RMQ)

Estructura de datos · Se implementa a mano · Tema: Estructuras de Datos Catálogo completo: Catálogo de estructuras

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

Responde el mínimo (o máx, gcd…) de un rango en O(1) tras un precálculo, para un arreglo ESTÁTICO.

Operaciones y costo

OperaciónCostoNotas
PrecálculoO(n log n)
Consultar mínimo/máximo de un rangoO(1)dos bloques solapados
Actualizar✗no admite cambios: para eso, segment tree
EspacioO(n log n)

Por dentro

Guarda el resultado de cada bloque de largo potencia de 2. Cualquier rango se cubre con dos bloques que se solapan — y eso funciona porque al mínimo (o al máximo) no le molesta contar dos veces lo mismo.

Cuándo usarla

Muchas consultas de mín/máx de rango sin actualizaciones. Base de LCA por Euler tour. No sirve si el arreglo cambia.

Implementación recomendada (C++)

struct SparseTable {                        // mínimo de rango
    vector<vector<int>> t; vector<int> lg;
    SparseTable(const vector<int>& a) {
        int n = a.size(), K = 1; while ((1 << K) <= n) K++;
        lg.assign(n + 1, 0); for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
        t.assign(K, vector<int>(n)); t[0] = a;
        for (int k = 1; k < K; k++)
            for (int i = 0; i + (1 << k) <= n; i++)
                t[k][i] = min(t[k-1][i], t[k-1][i + (1 << (k-1))]);
    }
    int query(int l, int r) {               // mínimo en [l, r] inclusive
        int k = lg[r - l + 1];
        return min(t[k][l], t[k][r - (1 << k) + 1]);
    }
};

⚠️ Notas

Funciona para operaciones idempotentes (mín, máx, gcd, AND/OR). Para suma no (cuentas dos veces); usa Fenwick (BIT) o Segment tree.

🔗 Relacionados