Estructuras de datos persistentes

Visión general

Una estructura de datos persistente es una estructura de datos que preserva las versiones anteriores de sí misma cuando se modifica, permitiendo acceder a cualquier versión histórica. En otras palabras, una vez que se hace un cambio a la estructura, tanto la versión original como la modificada permanecen accesibles. Esto es particularmente útil en escenarios donde se necesita rastrear el historial de actualizaciones o volver a estados anteriores de la estructura de datos.

Arreglo persistente

Los arreglos persistentes son una de las estructuras de datos persistentes más simples. Un arreglo persistente debería poder acceder y actualizar sus elementos en instantes dados.

Nodos gordos (Fat Nodes)

C++

En C++, se puede implementar esto para que corra en $\mathcal O(\log N)$ por consulta y $\mathcal O(1)$ por actualización usando un arreglo de vectors.


vector<pair<int, int>> arr[100001];  // The persistent array
 
int get_item(int index, int time) {
	// Gets the array item at a given index and time
	auto ub =
	    upper_bound(arr[index].begin(), arr[index].end(), make_pair(time, INT_MAX));
	return prev(ub)->second;
}
 
void update_item(int index, int value, int time) {
	// Updates the array item at a given index and time
	// Note that this only works if the time is later than all previous
	// update times
	assert(arr[index].back().first < time);
	arr[index].push_back({time, value});
}
 
void init_arr(int n, int *init) {
	// Initializes the persistent array, given an input array
	for (int i = 0; i < n; i++) arr[i].push_back({0, init[i]});
}

Este enfoque (es decir, guardar múltiples valores en cada índice sin borrar valores viejos) se conoce como nodos gordos (fat nodes).

Aunque es fácil de implementar, los nodos gordos son solo parcialmente persistentes, lo que significa que solo se puede modificar la última versión de la estructura de datos.

Para la mayoría de los problemas de programación competitiva que involucran estructuras de datos persistentes, usamos copia de camino (path copying) en su lugar.

Copia de camino

Se puede implementar la copia de camino para que corra en $\mathcal O(\log N)$ por consulta y actualización usando una estructura similar a un árbol binario donde los elementos del arreglo son las hojas.

Esto es muy similar a un Árbol de Segmentos disperso. Las diferencias clave son que tenemos múltiples raíces y cada vez que “actualizamos” un nodo, en realidad creamos un nodo nuevo en su lugar (de ahí la persistencia).

C++


struct Node {
	int val;
	Node *l, *r;
 
	Node(ll x) : val(x), l(nullptr), r(nullptr) {}
	Node(Node *ll, Node *rr) : val(0), l(ll), r(rr) {}
};
 
int n, a[100001];     // The initial array and its size
Node *roots[100001];  // The persistent array's roots
 
Node *build(int l = 0, int r = n - 1) {
	if (l == r) return new Node(a[l]);
	int mid = (l + r) / 2;
	return new Node(build(l, mid), build(mid + 1, r));
}
 
Node *update(Node *node, int val, int pos, int l = 0, int r = n - 1) {
	if (l == r) return new Node(val);
	int mid = (l + r) / 2;
	if (pos > mid) return new Node(node->l, update(node->r, val, pos, mid + 1, r));
	else return new Node(update(node->l, val, pos, l, mid), node->r);
}
 
int query(Node *node, int pos, int l = 0, int r = n - 1) {
	if (l == r) return node->val;
	int mid = (l + r) / 2;
	if (pos > mid) return query(node->r, pos, mid + 1, r);
	return query(node->l, pos, l, mid);
}
 
int get_item(int index, int time) {
	// Gets the array item at a given index and time
	return query(roots[time], index);
}
 
void update_item(int index, int value, int prev_time, int curr_time) {
	// Updates the array item at a given index and time
	roots[curr_time] = update(roots[prev_time], index, value);
}
 
void init_arr(int nn, int *init) {
	// Initializes the persistent array, given an input array
	n = nn;
	for (int i = 0; i < n; i++) a[i] = init[i];
	roots[0] = build();
}

La copia de camino es completamente persistente.

Árbol de Segmentos persistente

Como los arreglos persistentes con copia de camino son tan similares a los Árboles de Segmentos dispersos, es relativamente directo convertir uno en un Árbol de Segmentos persistente: ¡solo hay que agregar consultas de rango!

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Range Queries and Copies	Fácil		en el módulo

Recursos

Recursos
Fuente	Recurso	Notas
oml1111	PSeg Slides
Anudeep2011	PSegs w/ SPOJ	formato no muy bueno
cp-algo	Persistent Segment Tree
SecondThread	Persistent Data Structures	buen video sobre estructuras de datos persistentes

Solución

Como este problema involucra consultas de rango, usaremos algún tipo de Árbol de Segmentos para resolverlo. (También podemos usar un Árbol de Fenwick, pero es mucho más difícil hacerlo persistente.)

Cuando se lidia con problemas que involucran múltiples dimensiones, a menudo ayuda ver una de esas dimensiones como tiempo. En este problema, veremos el índice de cada arreglo como su dimensión temporal.

Usando un Árbol de Segmentos persistente, podemos entonces convertir el problema en lo siguiente:

Las consultas de tipo 1 involucran una actualización puntual en el Árbol de Segmentos en algún instante.
Las consultas de tipo 2 involucran una consulta de rango en el Árbol de Segmentos en algún instante.
Las consultas de tipo 3 involucran copiar la raíz del Árbol de Segmentos en algún instante y agregarla al arreglo de raíces de Árboles de Segmentos.

Complejidad temporal: $\mathcal{O}(N + Q\log{N})$

Implementación con punteros

C++


#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
struct Node {
	ll val;
	Node *l, *r;
 
	Node(ll x) : val(x), l(nullptr), r(nullptr) {}
	Node(Node *ll, Node *rr) {
		l = ll, r = rr;
		val = 0;
		if (l) val += l->val;
		if (r) val += r->val;
	}
	Node(Node *cp) : val(cp->val), l(cp->l), r(cp->r) {}
};
 
int n, cnt = 1;
ll a[200001];
Node *roots[200001];
 
Node *build(int l = 1, int r = n) {
	if (l == r) return new Node(a[l]);
	int mid = (l + r) / 2;
	return new Node(build(l, mid), build(mid + 1, r));
}
 
Node *update(Node *node, int val, int pos, int l = 1, int r = n) {
	if (l == r) return new Node(val);
	int mid = (l + r) / 2;
	if (pos > mid) return new Node(node->l, update(node->r, val, pos, mid + 1, r));
	else return new Node(update(node->l, val, pos, l, mid), node->r);
}
 
ll query(Node *node, int a, int b, int l = 1, int r = n) {
	if (l > b || r < a) return 0;
	if (l >= a && r <= b) return node->val;
	int mid = (l + r) / 2;
	return query(node->l, a, b, l, mid) + query(node->r, a, b, mid + 1, r);
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	roots[cnt++] = build();
 
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int k, i, x;
			cin >> k >> i >> x;
			roots[k] = update(roots[k], x, i);
		} else if (t == 2) {
			int k, l, r;
			cin >> k >> l >> r;
			cout << query(roots[k], l, r) << '\n';
		} else {
			int k;
			cin >> k;
			roots[cnt++] = new Node(roots[k]);
		}
	}
	return 0;
}

Implementación con índices

C++


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
class PersistentSegtree {
  private:
	struct Node {
		ll sum = 0;
		int l = 0, r = 0;
	};
 
	const int n;
	vector<Node> tree;
	int timer = 1;
 
	Node join(int l, int r) { return Node{tree[l].sum + tree[r].sum, l, r}; }
 
	int build(int tl, int tr, const vector<int> &arr) {
		if (tl == tr) {
			tree[timer] = {arr[tl], 0, 0};
			return timer++;
		}
 
		int mid = (tl + tr) / 2;
		tree[timer] = join(build(tl, mid, arr), build(mid + 1, tr, arr));
 
		return timer++;
	}
 
	int set(int v, int pos, int val, int tl, int tr) {
		if (tl == tr) {
			tree[timer] = {val, 0, 0};
			return timer++;
		}
 
		int mid = (tl + tr) / 2;
		if (pos <= mid) {
			tree[timer] = join(set(tree[v].l, pos, val, tl, mid), tree[v].r);
		} else {
			tree[timer] = join(tree[v].l, set(tree[v].r, pos, val, mid + 1, tr));
		}
 
		return timer++;
	}
 
	ll range_sum(int v, int ql, int qr, int tl, int tr) {
		if (qr < tl || tr < ql) { return 0ll; }
		if (ql <= tl && tr <= qr) { return tree[v].sum; }
 
		int mid = (tl + tr) / 2;
		return range_sum(tree[v].l, ql, qr, tl, mid) +
		       range_sum(tree[v].r, ql, qr, mid + 1, tr);
	}
 
  public:
	PersistentSegtree(int n, int MX_NODES) : n(n), tree(MX_NODES) {}
 
	int build(const vector<int> &arr) { return build(0, n - 1, arr); }
 
	int set(int root, int pos, int val) { return set(root, pos, val, 0, n - 1); }
 
	ll range_sum(int root, int l, int r) { return range_sum(root, l, r, 0, n - 1); }
 
	int add_copy(int root) {
		tree[timer] = tree[root];
		return timer++;
	}
};
 
int main() {
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for (int &i : a) { cin >> i; }
 
	const int MX_NODES = 2 * n + q * (2 + __lg(n));
	PersistentSegtree st(n, MX_NODES);
 
	vector<int> roots = {st.build(a)};
 
	for (int t = 0; t < q; t++) {
		int type, k;
		cin >> type >> k;
		k--;
 
		if (type == 1) {
			int pos, val;
			cin >> pos >> val;
			pos--;
			roots[k] = st.set(roots[k], pos, val);
		} else if (type == 2) {
			int a, b;
			cin >> a >> b;
			a--, b--;
			cout << st.range_sum(roots[k], a, b) << '\n';
		} else if (type == 3) {
			roots.push_back(st.add_copy(roots[k]));
		}
	}
}

En general, una implementación basada en índices es más rápida que una implementación con punteros.

Aplicación 1 - Sumas de rango 2D estáticas en grillas grandes

Los Árboles de Segmentos persistentes se pueden usar para consultas de suma de rango 2D estáticas online en $\mathcal O(\log N)$ (pensar en ello como sumas de prefijos).

Observar que los Árboles de Fenwick 2D con compresión de coordenadas a menudo también funcionan para esto (y son más fáciles de implementar), pero igual es bueno conocer esta aplicación.

Aplicación 2 - Intervalo más grande completamente dentro de un rango

Consideremos el siguiente problema:

Dados $N$ intervalos en la recta numérica, responder $Q$ consultas de la forma “¿cuál es el intervalo más grande completamente contenido dentro del rango $[x, y]$ ?”

$N, Q \leq 10^5$ .

Como cada intervalo tiene dos dimensiones (es decir, extremos izquierdo y derecho $l_i$ y $r_i$ ), podemos verlo como un punto en la recta numérica en $l_i$ con “valor” $r_i - l_i$ que fue insertado en el instante $r_i$ .

Ahora, cada consulta se convierte en “¿cuál es el punto más valioso en el rango $[x, y]$ que fue insertado en o antes del instante $y$ ?” Esto es mucho más fácil de manejar, así que podemos resolver este problema en $\mathcal O(Q \log N)$ .

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CF	Closest Equals	Fácil	Persistent Segtree	—
SPOJ	★ Count on a tree	Fácil	Persistent Segtree	Solución
SPOJ	Gao on a tree	Normal	Persistent Segtree	—
SPOJ	Query on a tree III	Normal	Persistent Segtree	—
SPOJ	K-th Number	Normal	Persistent Segtree	—
COCI	2021 - Index	Normal	Persistent Segtree	Solución
NOI	2010 - Super Piano	Normal	Persistent Segtree	—
CEOI	2020 - The Potion of Great Power	Difícil	Persistent Segtree, Sqrt	—
APIO	2017 - Land of the Rainbow Gold	Difícil	Persistent Segtree, Euler's Formula, 2DRQ	Solución
COCI	2020 - Specijacija	Muy difícil	Persistent Segtree	Solución
IOI	★ 2015 - Teams	Muy difícil	Persistent Segtree, 2DRQ	—

Heap persistente

Recursos
Fuente	Recurso	Notas
Benq	Leftist Heap

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Wesley's Anger Contest	Time Travelling Squirrels	Muy difícil		—
	YS	K-th Shortest Walk	Muy difícil		—