🧱 Segment tree con lazy propagation
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
Segment tree que soporta actualizaciones de rango (p.ej. sumar v a [l,r]) además de consultas de rango, difiriendo las actualizaciones.
Operaciones y costo
| Operación | Costo | Notas |
|---|---|---|
| Construir | O(n) | |
| Actualizar un RANGO | O(log n) | la diferencia con el segment tree normal |
| Consultar un rango | O(log n) | |
| Espacio | O(4n) | más el arreglo de marcas pendientes |
Por dentro
Cada nodo guarda una marca pendiente (‘a todo este segmento le falta sumar x’) que solo se empuja a los hijos cuando hace falta bajar. Así, actualizar un rango entero cuesta lo mismo que actualizar una posición.
Cuándo usarla
Cuando hay updates de rango (no solo puntuales): sumar/asignar en un intervalo y consultar suma/mín/máx.
Implementación recomendada (C++)
struct LazySeg { // range add, range sum
int n; vector<long long> t, lazy;
LazySeg(int n) : n(n), t(4*n, 0), lazy(4*n, 0) {}
void push(int nd, int l, int r) {
if (!lazy[nd]) return;
t[nd] += lazy[nd] * (r - l + 1);
if (l != r) { lazy[2*nd] += lazy[nd]; lazy[2*nd+1] += lazy[nd]; }
lazy[nd] = 0;
}
void update(int nd, int l, int r, int ql, int qr, long long v) {
push(nd, l, r);
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) { lazy[nd] += v; push(nd, l, r); return; }
int m = (l + r) / 2;
update(2*nd, l, m, ql, qr, v); update(2*nd+1, m+1, r, ql, qr, v);
t[nd] = t[2*nd] + t[2*nd+1];
}
long long query(int nd, int l, int r, int ql, int qr) {
push(nd, l, r);
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return t[nd];
int m = (l + r) / 2;
return query(2*nd, l, m, ql, qr) + query(2*nd+1, m+1, r, ql, qr);
}
// wrappers (raíz = 1, rango = [0, n-1])
void update(int l, int r, long long v) { update(1, 0, n - 1, l, r, v); }
long long query(int l, int r) { return query(1, 0, n - 1, l, r); }
};⚠️ Notas
La clave es push (bajar la lazy antes de descender). Para ‘asignar’ en vez de ‘sumar’ necesitas una lazy con bandera de set y combinarla con cuidado.