🧱 Segment tree persistente

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 donde cada actualización crea una versión NUEVA compartiendo nodos con la anterior, permitiendo consultar versiones pasadas.

Operaciones y costo

OperaciónCostoNotas
Crear una versión nuevaO(log n)tiempo y memoria
Consultar cualquier versiónO(log n)las anteriores siguen vivas
Espacio totalO(n + q log n)con q actualizaciones

Por dentro

Cada actualización copia solo el camino de la raíz a la hoja (log n nodos) y reutiliza todo el resto del árbol anterior. Las versiones viejas quedan intactas y consultables.

Cuándo usarla

Consultas sobre prefijos o versiones: k-ésimo en un rango, contar cuántos ≤ x en [l,r]. El truco se llama persistir por índice: la versión i contiene los primeros i elementos, así que la respuesta para [l,r] es la resta entre la versión r y la versión l-1.

Implementación recomendada (C++)

struct PersistentSeg {                      // suma puntual; cada update devuelve una raíz nueva
    struct Node { long long val = 0; int l = -1, r = -1; };
    vector<Node> t; int n;
    PersistentSeg(int n) : n(n) {}
    int build(int lo, int hi) {
        int id = t.size(); t.push_back({});
        if (lo < hi) { int m = (lo+hi)/2, L = build(lo,m), R = build(m+1,hi);
            t[id].l = L; t[id].r = R; }
        return id;
    }
    int update(int prev, int lo, int hi, int pos, long long add) {
        int id = t.size(); t.push_back(t[prev]); t[id].val += add;
        if (lo < hi) { int m = (lo+hi)/2;
            // el hijo se calcula en su propia variable ANTES de asignarlo: la llamada
            // hace push_back y puede reubicar el vector, invalidando cualquier
            // referencia a t[id] tomada antes de tiempo
            if (pos <= m) { int h = update(t[id].l, lo, m, pos, add); t[id].l = h; }
            else          { int h = update(t[id].r, m+1, hi, pos, add); t[id].r = h; }
        }
        return id;
    }
    long long query(int node, int lo, int hi, int ql, int qr) {
        if (node == -1 || qr < lo || hi < ql) return 0;
        if (ql <= lo && hi <= qr) return t[node].val;
        int m = (lo+hi)/2;
        return query(t[node].l, lo, m, ql, qr) + query(t[node].r, m+1, hi, ql, qr);
    }
};

⚠️ Notas

Reserva memoria de sobra: ~ (n + updates·log n) nodos. NO modifiques nodos viejos; cada update copia el camino raíz→hoja (path copying).

🔗 Relacionados