🧱 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ónCostoNotas
ConstruirO(n)
Actualizar un RANGOO(log n)la diferencia con el segment tree normal
Consultar un rangoO(log n)
EspacioO(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.

🔗 Relacionados