Tema 6
Sparse Table y manipulación de bits
Patrón de examen
Sparse Table para RMQ (Range Minimum Query) estático. Bitmask DP cuando el estado incluye un subconjunto de ≤20 elementos.
Explicación
Sparse Table
Estructura para consultas de mínimo/máximo en rango [l,r] en O(1) con precalculación O(n log n).
Solo funciona con operaciones idempotentes (min, max, GCD): f(f(x), x) = f(x).
No soporta actualizaciones (estático).
// Precalcular
sp[i][j] = min de a[i..i+2^j-1]
sp[i][0] = a[i]
sp[i][j] = min(sp[i][j-1], sp[i+2^(j-1)][j-1])
// Consulta O(1)
k = floor(log2(r-l+1))
min(l,r) = min(sp[l][k], sp[r-2^k+1][k])
Manipulación de bits
| Operación | Expresión C++ | Significado |
|---|---|---|
| Bit k activado? | (n >> k) & 1 | |
| Activar bit k | `n | (1 << k)` |
| Desactivar bit k | n & ~(1 << k) | |
| Alternar bit k | n ^ (1 << k) | |
| Quitar bit menos significativo | n & (n-1) | |
| Contar bits activos | __builtin_popcount(n) | |
| Bit menos significativo | n & (-n) |
Aplicaciones de bits
- Representar subconjuntos: un entero de k bits puede representar cualquier subconjunto de k elementos
- DP de subconjuntos (bitmask DP):
dp[mask]para máscara de bits - Compresión de estados