🧱 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ón | Costo | Notas |
|---|---|---|
| Precálculo | O(n log n) | |
| Consultar mínimo/máximo de un rango | O(1) | dos bloques solapados |
| Actualizar | ✗ | no admite cambios: para eso, segment tree |
| Espacio | O(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.