🧱 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ón | Costo | Notas |
|---|---|---|
| Crear una versión nueva | O(log n) | tiempo y memoria |
| Consultar cualquier versión | O(log n) | las anteriores siguen vivas |
| Espacio total | O(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).