Árboles de Segmentos dispersos

En problemas donde el rango de consulta es a lo sumo algo como $10^6$ , un árbol de segmentos normal alcanza. Sin embargo, en cuanto pasamos a rangos más grandes ( $10^{12}$ en algunos casos), un árbol de segmentos normal termina en MLE.

Por suerte, todavía podemos usar un árbol de segmentos para resolver este tipo de problemas. La idea principal es que no hace falta guardar todos los nodos en todo momento: creamos nodos solo cuando se necesitan. En un árbol de segmentos normal, una actualización solo afecta $\mathcal{O}(\log N)$ nodos, así que en un árbol de segmentos disperso solo guardamos $\mathcal{O}(Q \log N)$ nodos.

Podemos implementar esto de forma eficiente usando punteros a los hijos de un nodo, ¡igual que un trie! (De hecho, un árbol de segmentos es básicamente un trie binario más sofisticado.)

Una alternativa es implementar los nodos usando índices y un arreglo para llevar el registro de cada nodo. Esto suele ser más rápido que usar punteros, aunque es un poco menos natural de implementar.

Recursos

Recursos
Fuente	Recurso	Notas
Benq	Implementation
cp-algo	Dynamic segment tree

Monkey and Apple-trees

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	IZhO	2012 - Monkey and Apple-trees	Normal		en el módulo

Solución

Hay que soportar dos operaciones sobre un rango:

Contar la cantidad de árboles red-ripe en un rango (suma de rango)
Poner todos los árboles de un rango en red-ripe (pintar un rango)

Podemos usar un árbol de segmentos con propagación perezosa para resolver esto, pero el rango de consulta llega hasta $10^9$ , así que hay que usar un árbol de segmentos disperso.

Por suerte, la propagación perezosa sigue funcionando acá.

Implementación con punteros

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

C++


#include <bits/stdc++.h>
using namespace std;
 
class SparseSegtree {
  private:
	struct Node {
		int freq = 0;
		int lazy = 0;
		Node *left = nullptr;
		Node *right = nullptr;
	};
	Node *root = new Node;
	const int n;
 
	int comb(int a, int b) { return a + b; }
 
	void apply(Node *cur, int len, int val) {
		if (val == 1) {
			(cur->lazy) = val;
			(cur->freq) = len * val;
		}
	}
 
	void push_down(Node *cur, int l, int r) {
		if ((cur->left) == nullptr) { (cur->left) = new Node; }
		if ((cur->right) == nullptr) { (cur->right) = new Node; }
		int m = (l + r) / 2;
		apply(cur->left, m - l + 1, cur->lazy);
		apply(cur->right, r - m, cur->lazy);
	}
 
	void range_set(Node *cur, int l, int r, int ql, int qr, int val) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(cur, r - l + 1, val);
		} else {
			push_down(cur, l, r);
			int m = (l + r) / 2;
			range_set(cur->left, l, m, ql, qr, val);
			range_set(cur->right, m + 1, r, ql, qr, val);
			(cur->freq) = comb((cur->left)->freq, (cur->right)->freq);
		}
	}
 
	int range_sum(Node *cur, int l, int r, int ql, int qr) {
		if (qr < l || ql > r) { return 0; }
		if (ql <= l && r <= qr) { return cur->freq; }
		push_down(cur, l, r);
		int m = (l + r) / 2;
		return comb(range_sum(cur->left, l, m, ql, qr),
		            range_sum(cur->right, m + 1, r, ql, qr));
	}
 
  public:
	SparseSegtree(int n) : n(n) {}
 
	void range_set(int ql, int qr, int val) { range_set(root, 0, n - 1, ql, qr, val); }
 
	int range_sum(int ql, int qr) { return range_sum(root, 0, n - 1, ql, qr); }
};
 
int main() {
	int query_num;
	cin >> query_num;
	const int RANGE_SIZE = 1e9;
	SparseSegtree st(RANGE_SIZE + 1);
 
	int c = 0;
	for (int i = 0; i < query_num; i++) {
		int type, x, y;
		cin >> type >> x >> y;
		if (type == 1) {
			c = st.range_sum(x + c, y + c);
			cout << c << '\n';
		} else if (type == 2) {
			st.range_set(x + c, y + c, 1);
		}
	}
}

Implementación con índices

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

C++


#include <bits/stdc++.h>
using namespace std;
 
class SparseSegtree {
  private:
	struct Node {
		int freq = 0;
		int lazy = 0;
		int left = -1;
		int right = -1;
	};
	vector<Node> tree;
	const int n;
	int timer = 0;
 
	int comb(int a, int b) { return a + b; }
 
	void apply(int cur, int len, int val) {
		if (val == 1) {
			tree[cur].lazy = val;
			tree[cur].freq = len * val;
		}
	}
 
	void push_down(int cur, int l, int r) {
		if (tree[cur].left == -1) {
			tree[cur].left = ++timer;
			tree.push_back(Node());
		}
		if (tree[cur].right == -1) {
			tree[cur].right = ++timer;
			tree.push_back(Node());
		}
		int m = (l + r) / 2;
		apply(tree[cur].left, m - l + 1, tree[cur].lazy);
		apply(tree[cur].right, r - m, tree[cur].lazy);
		tree[cur].lazy = 0;
	}
 
	void range_set(int cur, int l, int r, int ql, int qr, int val) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(cur, r - l + 1, val);
		} else {
			push_down(cur, l, r);
			int m = (l + r) / 2;
			range_set(tree[cur].left, l, m, ql, qr, val);
			range_set(tree[cur].right, m + 1, r, ql, qr, val);
			tree[cur].freq =
			    comb(tree[tree[cur].left].freq, tree[tree[cur].right].freq);
		}
	}
 
	int range_sum(int cur, int l, int r, int ql, int qr) {
		if (qr < l || ql > r) { return 0; }
		if (ql <= l && r <= qr) { return tree[cur].freq; }
		push_down(cur, l, r);
		int m = (l + r) / 2;
		return comb(range_sum(tree[cur].left, l, m, ql, qr),
		            range_sum(tree[cur].right, m + 1, r, ql, qr));
	}
 
  public:
	SparseSegtree(int n, int q = 0) : n(n) {
		if (q > 0) { tree.reserve(2 * q * __lg(n)); }
		tree.push_back(Node());
	}
 
	void range_set(int ql, int qr, int val) { range_set(0, 0, n - 1, ql, qr, val); }
 
	int range_sum(int ql, int qr) { return range_sum(0, 0, n - 1, ql, qr); }
};
 
int main() {
	int query_num;
	cin >> query_num;
	const int RANGE_SIZE = 1e9;
	SparseSegtree st(RANGE_SIZE + 1, query_num);
 
	int c = 0;
	for (int i = 0; i < query_num; i++) {
		int type, x, y;
		cin >> type >> x >> y;
		if (type == 1) {
			c = st.range_sum(x + c, y + c);
			cout << c << '\n';
		} else if (type == 2) {
			st.range_set(x + c, y + c, 1);
		}
	}
}

Opcional

Es posible reducir la memoria de un árbol de segmentos disperso a $\mathcal{O}(Q)$ , como se describe aquí .

Problemas

Algunos de estos problemas se pueden resolver con un árbol de segmentos normal si se usa compresión de coordenadas. Los árboles de segmentos dispersos rara vez son imprescindibles para resolver un problema en particular, pero pueden hacer las cosas mucho más cómodas.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	IOI	2005 - Mountain	Normal	Sparse Segtree, Lazy SegTree	Solución
	Balkan OI	2015 - Happiness	Normal		Solución