Sparse Table es una estructura para range queries idempotentes (min, max, gcd) en O(1) tras preprocesamiento O(n log n). Es más simple que segment tree y más rápida en query, pero no soporta updates.
La idea: precomputa respuestas para intervalos de longitud potencia de 2, y combina dos intervalos para cubrir cualquier rango.
Build
st[i][k] = resultado sobre arr[i..i+2^k-1].
st[i][0] = arr[i]
st[i][k] = combine(st[i][k-1], st[i + 2^{k-1}][k-1])Complejidad: O(n log n) porque hay n log n entradas.
Query
Para rango [L, R] (longitud len = R-L+1):
k = floor(log2(len))
result = combine(st[L][k], st[R - 2^k + 1][k])Los dos intervalos de longitud 2^k se superponen pero para operaciones idempotentes (min, max, gcd) eso no importa.
Ejemplo
Array: [3, 1, 4, 1, 5, 9], query min en [2, 5] (0-based: 4, 1, 5, 9).
len = 4, k = log2(4) = 2.
st[2][2] = min en [2, 5] = 1.
Limitaciones
- Sin updates — si el array cambia, debes rebuild.
- Solo idempotentes — no funciona para suma (necesitas ranges sin superposición).
- Espacio — O(n log n) vs O(n) de Fenwick.
Comparación
| Estructura | Query | Update | Build | Uso |
|---|---|---|---|---|
| Sparse Table | O(1) | No | O(n log n) | Min/Max estático |
| Segment Tree | O(log n) | Sí | O(n) | General |
| Fenwick | O(log n) | Sí | O(n) | Suma |
Aplicaciones
- Range min/max — RMQ en arrays estáticos
- LCA — Lowest Common Ancestor en árboles
- GCD queries — matemáticas, criptografía
- Enseñanza — introduce sparse representation y queries O(1)
Trayectoria de Práctica
- Implementa sparse table para RMQ; traza query.
- Verifica que O(1) query es correcta.
- Extiende a GCD.
- Investiga por qué suma no es idempotente.
- Investiga LCA con sparse table: ¿cómo usa binary lifting?