Tema 5
Segment Tree y Fenwick Tree
Patrón de examen
Fenwick para sumas con actualizaciones puntuales (más simple). Segment Tree cuando necesites min/max/GCD en rangos o actualizaciones de rangos con lazy propagation.
Explicación
Fenwick Tree (Binary Indexed Tree)
Estructura que soporta en O(log n):
- Actualizar un elemento (sumar un valor)
- Consultar la suma de prefijo [1, i]
Más simple de implementar que Segment Tree. Ideal para sumas y frecuencias.
void update(int i, int v) { for (; i <= n; i += i&(-i)) bit[i] += v; }
int query(int i) { int s=0; for (; i > 0; i -= i&(-i)) s += bit[i]; return s; }
int query(int l, int r) { return query(r) - query(l-1); }
Segment Tree
Más general que Fenwick. Soporta en O(log n):
- Suma, mínimo, máximo, GCD en rangos
- Actualizaciones puntuales (y con lazy propagation: rangos)
Cuándo usar cada uno:
- Fenwick → sumas/frecuencias con actualizaciones puntuales
- Segment Tree → operaciones más complejas (min, max, GCD) o lazy propagation