Treaps

Recursos
Fuente	Recurso	Notas
GCP	15.3 - Treaps	Split y merge con código
cp-algo	Treap	Descripción y código
Algorithm Tutorial	Treaps : One Tree to Rule ’em all	Código y diagramas
Benq	Treap presentation	Descripción de Split y Merge
CF	Merging BSTs	Demostración de la complejidad temporal de fusionar treaps

Treaps

Como un árbol binario de búsqueda habitual, los treaps contienen claves que se pueden insertar, borrar y buscar en $\mathcal{\Theta}(\log n)$ . Sin embargo, los árboles binarios de búsqueda habituales sufren de desbalanceo, lo que hace que el árbol tenga hasta $\mathcal{O}(n)$ de profundidad y dispare la complejidad temporal.

Unbalanced Binary Search Tree

Un treap es un árbol binario de búsqueda aleatorizado que guarda dos números en sus nodos: un valor y una prioridad. Los valores de un treap cumplen la propiedad de árbol binario de búsqueda (todos los nodos del subárbol izquierdo son estrictamente menores que el nodo actual y todos los nodos del subárbol derecho son estrictamente mayores que el nodo actual), y las prioridades cumplen la propiedad de heap (todos los descendientes de un nodo tienen prioridades menores o iguales).

Treap

Los treaps tienen dos operaciones principales: split y merge. Otras operaciones como insertar, borrar y buscar se pueden implementar en términos de estas.

Split

El método split recibe un puntero a la raíz de un treap $\texttt{root}$ y un valor $x$ , y devuelve dos treaps denotados $\texttt{left}$ y $\texttt{right}$ . Como sugiere el nombre, parte el árbol de modo que todos los nodos de $\texttt{left}$ tienen claves menores o iguales que $x$ y todos los nodos de $\texttt{right}$ tienen claves mayores que $x$ .

Ahora lo podemos implementar de forma recursiva. Denotemos el hijo izquierdo de un nodo $n$ como $n.\texttt{left}$ y el hijo derecho como $n.\texttt{right}$ .

Si $\texttt{root} \leq x$ , entonces tanto la raíz como el subárbol izquierdo pertenecen a $\texttt{left}$ . Ahora consideramos una llamada a split sobre $\texttt{root.right}$ y anotamos sus resultados como $\texttt{left'}$ y $\texttt{right'}$ . Finalmente, $\texttt{left}$ contiene $\texttt{left'}$ y $\texttt{right} = \texttt{right'}$ .
Si $\texttt{root} > x$ , entonces tanto la raíz como el subárbol derecho pertenecen a $\texttt{right}$ . Ahora consideramos una llamada a split sobre $\texttt{root.left}$ y anotamos sus resultados como $\texttt{left'}$ y $\texttt{right'}$ . Finalmente, $\texttt{right}$ contiene $\texttt{right'}$ y $\texttt{left} = \texttt{left'}$ .

Merge

El método merge invierte el método split tomando dos treaps $\texttt{left}$ y $\texttt{right}$ y devolviendo un solo treap que tiene los nodos de ambos. Funciona bajo el supuesto de que todas las claves $x \in \texttt{left}$ son estrictamente menores que todas las claves $y \in \texttt{right}$ . Además, hay que fusionar estos dos treaps de modo que el treap resultante siga cumpliendo la propiedad de max-heap.

Enraizamos el treap resultante en el nodo raíz de mayor prioridad, y llamamos recursivamente a merge sobre el otro árbol y el subárbol correspondiente del árbol elegido.

Implementación

C++


#include <stdlib.h>
 
struct Node {
	// el valor y la prioridad del nodo respectivamente
	int val, pri;
	// puntero al hijo izquierdo y derecho (NULL significa sin hijo)
	Node *left, *right;
	Node(int val) : val(val), pri(rand()), left(NULL), right(NULL){};
} *root;
 
/**
 * pasar root como puntero, left y right como referencias
 * a un puntero a nodo para poder modificarlos
 * (alternativamente, se pueden devolver los punteros left y right
 * como un std::pair)
 */
void split(Node *root, int x, Node *&left, Node *&right) {
	if (!root) {
		left = right = NULL;
		return;
	}
	if (root->val <= x) {
		split(root->right, x, root->right, right);
		left = root;
	} else {
		split(root->left, x, left, root->left);
		right = root;
	}
}
 
/**
 * fusionar los punteros left y right en root, que
 * es una referencia a un puntero para permitir
 * la modificación dentro de la función
 */
void merge(Node *&root, Node *left, Node *right) {
	if (!left || !right) {
		root = left ? left : right;
		return;
	}
	if (left->pri > right->pri) {
		merge(left->right, left->right, right);
		root = left;
	} else {
		merge(right->left, left, right->left);
		root = right;
	}
}

Opcional

Por velocidad / memoria, usar arreglos de tamaño fijo en lugar de punteros.

Treaps implícitos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Cut and Paste	Fácil		en el módulo

En su forma más básica, los treaps no son muy útiles (lenguajes como C++ y Java ya tienen un árbol binario auto-balanceado incorporado que es mucho más eficiente que los treaps). Sin embargo, con treaps implícitos, podemos realizar operaciones de forma eficiente sobre un arreglo habitual de manera similar a los árboles de segmentos y a los Árboles de Fenwick. Las siguientes operaciones las soportan los treaps implícitos:

Insertar un elemento $x$ en la posición $i$
Eliminar el elemento en la posición $i$
Realizar consultas de intervalo (suma, mín, máx, etc.)
Realizar actualizaciones de intervalo (sumar, asignar, invertir, etc.)

La clave de los treaps implícitos está en su nombre. Usaremos el índice del nodo como su clave. Como mantener este valor de forma explícita implicaría actualizar hasta $\mathcal{O}(n)$ valores por inserción/eliminación, lo mantendremos de forma implícita.

El índice de un nodo es igual a la cantidad de nodos menores que él. Es importante notar que estos nodos pueden aparecer tanto en el subárbol izquierdo del nodo actual como en los ancestros del nodo y en el subárbol izquierdo de sus ancestros.

Nótese que en un treap implícito, la función merge queda en gran medida igual porque no depende de la clave. En la operación split bajamos desde la raíz, así que simplemente mantenemos un conteo acumulado del tamaño del subárbol izquierdo.

Una implementación de la operación split puede verse así:

C++


void split(Node *treap, Node *&left, Node *&right, int val, int add = 0) {
	if (!treap) {
		left = right = NULL;
		return;
	}
 
	int cur_size = add + size(treap->left);  // clave implícita
	if (cur_size < val) {
		split(treap->right, treap->right, right, val, add + 1 + size(treap->left));
		left = treap;
	} else {
		split(treap->left, left, treap->left, val, add);
		right = treap;
	}
	treap->size = 1 + size(treap->left) + size(treap->right);
}

En la operación split, como siempre comparamos $\texttt{cur\\_size}$ con $\texttt{val}$ , podemos eliminar el parámetro $\texttt{add}$ restando de $\texttt{val}$ cada vez. El código nuevo queda así:

C++


void split(Node *treap, Node *&left, Node *&right, int val) {
	if (!treap) {
		left = right = NULL;
		return;
	}
 
	if (size(treap->left) < val) {
		split(treap->right, treap->right, right, val - size(treap->left) - 1);
		left = treap;
	} else {
		split(treap->left, left, treap->left, val);
		right = treap;
	}
	treap->size = 1 + size(treap->left) + size(treap->right);
}

Implementación

C++


struct Node {
	int val;
	int weight, size;
	Node *left, *right;
	Node(int c) : val(c), weight(rand()), size(1), left(NULL), right(NULL) {}
} *root;
 
int size(Node *treap) { return treap ? treap->size : 0; }
 
void split(Node *treap, Node *&left, Node *&right, int val) {
	if (!treap) {
		left = right = NULL;
		return;
	}
 
	if (size(treap->left) < val) {
		split(treap->right, treap->right, right, val - size(treap->left) - 1);
		left = treap;
	} else {
		split(treap->left, left, treap->left, val);
		right = treap;
	}
	treap->size = 1 + size(treap->left) + size(treap->right);
}
 
void merge(Node *&treap, Node *left, Node *right) {
	if (left == NULL) {
		treap = right;
		return;
	}
	if (right == NULL) {
		treap = left;
		return;
	}
 
	if (left->weight < right->weight) {
		merge(left->right, left->right, right);
		treap = left;
	} else {
		merge(right->left, left, right->left);
		treap = right;
	}
	treap->size = 1 + size(treap->left) + size(treap->right);
}

Solución

Usaremos treaps implícitos para representar el arreglo. Para cada operación, la dividimos en dos fases: cortar y pegar. Para la fase de corte, partimos el arreglo en tres partes: $[1, a)$ , $[a, b]$ y $(b, n]$ . Esto se logra con dos operaciones split. Para la fase de pegado, podemos reordenar las secciones de modo que las fusionemos en el orden $[1, a)$ $(b, n]$ $[a, b]$ . Esto se hace con dos operaciones merge.

C++


#include <bits/stdc++.h>
using namespace std;
 
struct Node {
	char val;
	int weight, size;
	Node *left, *right;
	Node(char c) : val(c), weight(rand()), size(1), left(NULL), right(NULL) {}
} *root;
 
inline int size(Node *treap) { return treap ? treap->size : 0; }
 
void split(Node *treap, Node *&left, Node *&right, int val) {
	if (!treap) {
		left = right = NULL;
		return;
	}
 
	if (size(treap->left) < val) {
		split(treap->right, treap->right, right, val - size(treap->left) - 1);
		left = treap;
	} else {
		split(treap->left, left, treap->left, val);
		right = treap;
	}
	treap->size = 1 + size(treap->left) + size(treap->right);
}
 
void merge(Node *&treap, Node *left, Node *right) {
	if (left == NULL) {
		treap = right;
		return;
	}
	if (right == NULL) {
		treap = left;
		return;
	}
 
	if (left->weight < right->weight) {
		merge(left->right, left->right, right);
		treap = left;
	} else {
		merge(right->left, left, right->left);
		treap = right;
	}
	treap->size = 1 + size(treap->left) + size(treap->right);
}
 
ostream &operator<<(ostream &os, Node *n) {
	if (!n) return os;
	os << n->left;
	os << n->val;
	os << n->right;
	return os;
}
 
int main() {
	int N, Q;
	string S;
 
	cin >> N >> Q >> S;
	for (char c : S) { merge(root, root, new Node(c)); }
	while (Q--) {
		int l, r;
		cin >> l >> r;
		Node *a, *b, *c, *d;
		split(root, a, b, l - 1);
		split(b, c, d, r - l + 1);
		merge(root, a, d);
		merge(root, root, c);
	}
	cout << root << '\n';
}

Los treaps implícitos también son capaces de actualizaciones/eliminaciones de elementos, consultas de rango, actualizaciones de rango e inversiones de rango.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	★ Dynamic Sequence Range Affine Range Sum	Fácil	Treap	en el módulo

Insert se puede hacer con un split y dos merges: partimos el arreglo en el índice donde queremos insertar, creamos un nodo nuevo con el valor correspondiente y fusionamos las tres secciones.
Delete se puede hacer con dos splits y un merge: partimos el arreglo en tres partes antes y después del índice, y fusionamos las dos partes restantes.
Las consultas de rango se pueden realizar manteniendo datos adicionales en cada nodo. Actualizamos estos datos cada vez que actualizamos $\texttt{size}$ .
Las actualizaciones de rango se pueden realizar manteniendo una etiqueta perezosa (lazy tag) en cada nodo (como en la propagación perezosa). Al hacer split o merge, empujamos estas etiquetas hacia abajo y realizamos la operación correspondiente.
Las inversiones de rango se pueden realizar manteniendo una etiqueta perezosa reversed en cada nodo. Al hacer split o merge, primero intercambiamos los hijos izquierdo y derecho del nodo, y luego empujamos la etiqueta hacia abajo.

Implementación

Este código resuelve el problema de arriba, pero también ofrece una plantilla generalizable para cualquier actualización/consulta de rango.

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

C++


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
// BeginCodeSnip{ModInt class}
// operaciones bajo módulo
struct mint {
	const static int M = 998244353;
	ll v = 0;
	mint() {}
	mint(ll v) { this->v = (v % M + M) % M; }
	mint operator+(const mint &o) const { return v + o.v; }
	mint &operator+=(const mint &o) {
		v = (v + o.v) % M;
		return *this;
	}
	mint operator*(const mint &o) const { return v * o.v; }
	mint operator-(const mint &o) const { return v - o.v; }
	mint &operator-=(const mint &o) {
		mint t = v - o.v;
		v = t.v;
		return *this;
	}
	mint operator^(int y) const {
		mint r = 1, x = v;
		for (y <<= 1; y >>= 1; x = x * x)
			if (y & 1) r = r * x;
		return r;
	}
	mint inv() const {
		assert(v);
		return *this ^ M - 2;
	}
	friend istream &operator>>(istream &s, mint &v) {
		return s >> v.v;
		return s;
	}
	friend ostream &operator<<(ostream &s, const mint &v) { return s << v.v; }
	mint operator/(mint o) { return *this * o.inv(); }
};
// EndCodeSnip
 
struct Line {  // función lineal wx + b
	mint w = 1, b = 0;
	mint operator()(mint x) { return w * x + b; }
	Line operator()(Line f) { return Line{w * f.w, w * f.b + b}; }
	operator bool() const {
		return w.v != 1 || b.v != 0;
	}  // falso si esta es la función identidad
};
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
struct Node {
	Node(mint val) : val(val), sum(val), weight(rng()), size(1) {}
	mint val, sum;  // val -> a[i], sum = suma de todos los a[i] del subárbol
	ll weight, size;
	bool rev = false;  // si este rango está invertido
	Node *l = nullptr, *r = nullptr;
	Line f;  // etiqueta perezosa afín
};
 
int size(Node *treap) { return treap ? treap->size : 0; }
 
mint sum(Node *treap) { return treap ? treap->sum : 0; }
 
void push(Node *treap) {
	if (!treap) { return; }
	if (treap->rev) {  // hay que invertir este rango
		treap->rev = false;
		swap(treap->l, treap->r);
		if (treap->l) { treap->l->rev ^= true; }
		if (treap->r) { treap->r->rev ^= true; }
	}
	if (treap->f) {  // hay que aplicar la afín a este rango
		treap->val = treap->f(treap->val);
		treap->sum = treap->f.w * treap->sum + treap->f.b * treap->size;
		if (treap->l) { treap->l->f = treap->f(treap->l->f); }
		if (treap->r) { treap->r->f = treap->f(treap->r->f); }
		treap->f = Line{1, 0};
	}
}
 
void pull(Node *treap) {
	if (!treap) { return; }
	push(treap->l), push(treap->r);
	assert(!treap->f);
	treap->size = size(treap->l) + size(treap->r) + 1;
	treap->sum = sum(treap->l) + sum(treap->r) + treap->val;
}
 
// fusiona los treaps l y r en treap
void merge(Node *&treap, Node *l, Node *r) {
	push(l), push(r);
	if (!l || !r) {
		treap = l ? l : r;
	} else if (l->weight > r->weight) {
		merge(l->r, l->r, r), treap = l;
	} else {
		merge(r->l, l, r->l), treap = r;
	}
	pull(treap);
}
 
// parte treap en l, r; l: [0, val), r: [val, )
void split(Node *treap, Node *&l, Node *&r, int val) {
	if (!treap) return void(l = r = nullptr);
	push(treap);
	if (val > size(treap->l)) {
		split(treap->r, treap->r, r, val - size(treap->l) - 1), l = treap;
	} else {
		split(treap->l, l, treap->l, val), r = treap;
	}
	pull(treap);
}
 
struct Treap {
	Node *root = nullptr;  // raíz de este treap
 
	void insert(int i, int x) {
		Node *l, *r;
		split(root, l, r, i);
		auto v = new Node(x);
		merge(l, l, v);
		merge(root, l, r);
	}
 
	void del(int i) {
		Node *l, *r;
		split(root, l, r, i);
		split(r, root, r, 1);
		merge(root, l, r);
	}
 
	/**
	 * actualiza el rango [l, r)
	 * @param f la función a aplicar al rango
	 */
	void upd(int l, int r, function<void(Node *)> f) {
		Node *a, *b, *c;  // a: [0, l); b: [l, r); c: [r, )
		split(root, a, b, l);
		split(b, b, c, r - l);
		if (b) { f(b); }
		// fusionar todos los splits de vuelta al treap principal
		merge(root, a, b);
		merge(root, root, c);
	}
 
	/**
	 * consulta el rango [l, r)
	 * @param f una función de consulta (ver uso más abajo)
	 */
	template <typename R> R query(int l, int r, function<R(Node *)> f) {
		Node *a, *b, *c;  // a: [0, l); b: [l, r); c: [r, )
		split(root, a, b, l);
		split(b, b, c, r - l);
		assert(b);
		R x = f(b);
		merge(root, a, b);
		merge(root, root, c);
		return x;
	}
};
 
int main() {
	int n, q;
	cin >> n >> q;
	Treap treap;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		treap.insert(i, x);
	}
 
	for (int query = 0; query < q; query++) {
		int t;
		cin >> t;
		int i, x, l, r, w, b;
		switch (t) {
		case 0:
			cin >> i >> x;
			treap.insert(i, x);
			break;
		case 1:
			cin >> i;
			treap.del(i);
			break;
		case 2:
			cin >> l >> r;
			treap.upd(l, r, [](Node *x) { x->rev ^= true; });
			break;
		case 3:
			cin >> l >> r >> w >> b;
			treap.upd(l, r, [=](Node *x) { x->f = Line{w, b}(x->f); });
			break;
		case 4:
			cin >> l >> r;
			cout << treap.query<mint>(l, r, [](Node *x) { return x->sum; }) << endl;
			break;
		}
	}
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Substring Reversals	Fácil	Treap	Solución
CSES	Reversals and Sums	Fácil	Treap	—
POI	2011 - Tree Rotations 2	Normal	Treap	Solución
NOI	Maintaining a Sequence	Normal	Treap	—
Old Gold	Airplane Boarding	Normal	Treap	—
CSA	Strings	Normal	Treap	—
HE	Points and Distances	Normal	Treap	—
IOI	2013 - Game	Difícil	2DRQ, Sparse SegTree, Treap	Solución