Actualización de rango y consulta de rango

BIT revisitado

Los Árboles de Fenwick pueden soportar incrementos de rango y consultas de suma de rango.

Recursos

Recursos
Fuente	Recurso	Notas
CF	Historic Sums and Range Add Range Sum
GFG	Range Update Point Query
GFG	Range Update Range Query

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	SPOJ	Horrible Queries	Fácil	1DRQ	en el módulo

Explicación

Primero, podemos reducir el problema de hacer adiciones de rango y consultas de suma de rango a un problema más fácil: sumar sobre un sufijo, y consultar la suma de un prefijo de nuestro arreglo.

Sea $a$ nuestro arreglo, y $b$ el arreglo de sumas de prefijos de $a$ . Si sumamos $x$ al rango $[p, n]$ , entonces, para cada $i \geq p$ , sumamos $x \cdot (i - p + 1)$ a cada $b_i$ del rango. Para consultar el prefijo $[1, p]$ , podemos considerar el siguiente proceso:

Hallar la suma de todas las adiciones de rango que afectan al índice $p$ . Sea este número $x$ . Por ahora, evaluamos su contribución como $p \cdot x$ . Podemos llevar el registro de todas las adiciones de rango que afectan a cada índice usando un BIT.
El paso 1 obviamente sobrecuenta. Para corregir este sobreconteo, notar que para cada consulta de adición de sufijo, la contribución verdadera al arreglo solo difiere en una cantidad constante respecto del valor obtenido en el paso 1. Este valor es $x \cdot (p - 1)$ , si actualizamos el sufijo $[p, n]$ sumando $x$ . Así, usamos un BIT separado que lleva el registro de todas las correcciones a la contribución evaluada en el paso 1.

Podemos hacer consultas de adición de rango y suma de rango haciendo varias consultas de adición de sufijo y suma de prefijo.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{BIT Code (from PURS module)}
template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;
 
  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}
 
	void set(int ind, T val) { add(ind, val - arr[ind]); }
 
	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}
 
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};
// EndCodeSnip
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, q;
		cin >> n >> q;
 
		BIT<long long> bit_values(n + 1);
		BIT<long long> bit_count(n + 1);
		for (int i = 0; i < q; i++) {
			int type;
			cin >> type;
 
			if (type == 0) {
				int p, q, val;
				cin >> p >> q >> val;
				p--, q--;
 
				// Actualizar los 2 BIT
				bit_values.add(p, val);
				bit_count.add(p, 1ll * val * (p - 1));
				bit_values.add(q + 1, -val);
				bit_count.add(q + 1, -1ll * val * q);
			} else {
				int p, q;
				cin >> p >> q;
				p--, q--;
				long long pref_p =
				    bit_values.pref_sum(p - 1) * (p - 1) - bit_count.pref_sum(p - 1);
				long long pref_q = bit_values.pref_sum(q) * q - bit_count.pref_sum(q);
				cout << pref_q - pref_p << '\n';
			}
		}
	}
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Polynomial Queries	Fácil	1DRQ	—
Baltic OI	2011 - Growing Trees	Normal	1DRQ, Binary Search	Solución
IOI	★ 2007 - Sails	Normal	1DRQ, Binary Search	Solución

Árbol de Segmentos perezoso

Los árboles de segmentos perezosos nos permiten hacer de forma eficiente actualizaciones de rango y consultas de rango.

Recursos
Fuente	Recurso	Notas
CF EDU	Segment Tree Pt 2
CPH	28.1 - Segment Trees Revisited	descripción corta
CSA	Segment Trees	interactivo
cp-algo	Segment Tree	sumar sobre segmentos, asignar
CF	Efficient and easy segment trees	el código es más confuso que la versión recursiva

Los árboles de segmentos perezosos nos permiten hacer actualizaciones de rango y consultas de rango en tiempo $\mathcal{O}(\log{N})$ . Para hacer actualizaciones de rango en $\mathcal{O}(\log{N})$ , aplicamos actualizaciones de forma perezosa a los nodos. Es decir, guardamos las actualizaciones en los nodos que componen el rango que estamos actualizando, y las aplicamos de forma perezosa cuando bajamos por el árbol.

Como ejemplo, consideremos escribir un árbol de segmentos perezoso que soporte adición de rango y suma de rango. Haríamos que los nodos del árbol contengan la suma sobre el rango, y guardaríamos un arreglo separado con las adiciones perezosas que hay que hacer para cada nodo. Si sumáramos $3$ a nuestro arreglo $a[0 \ldots n - 1]$ , entonces necesitaríamos poner una actualización perezosa en la raíz del árbol indicando que hay que sumar $3$ a todo el rango. Después, si consultáramos un subarreglo de $a$ , hay que “empujar hacia abajo” (push down) las actualizaciones de la raíz a sus hijos.

Es crucial que siempre empujemos hacia abajo todas las actualizaciones previas al bajar por el árbol. Si no lo hacemos, puede pasar lo siguiente:

Si tenemos dos actualizaciones que afectan a dos nodos, donde un nodo es ancestro de otro, entonces una de las actualizaciones se ignorará.
Las actualizaciones se aplicarán en orden incorrecto, lo que importa si las actualizaciones no son conmutativas.

Para un ejemplo concreto de por qué el punto 1 puede ser un problema, considerar la siguiente secuencia de actualizaciones.

$+3$ a todos los valores de $[1, 4]$
$+5$ a todos los valores de $[1, 2]$
Consultar la suma de $[1, 8]$

Si no empujamos las actualizaciones al bajar por el árbol, entonces la primera actualización se ignora en nuestra consulta de suma.

Implementación de Horrible Queries

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

C++


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
template <typename T> class LazySegtree {
  private:
	const int sz;
	vector<T> tree;
	vector<T> lazy;
 
	/** aplica la actualización perezosa a tree[v], la coloca en lazy[v] */
	void apply(int v, int len, T add) {
		tree[v] += add * len;
		lazy[v] += add;
	}
 
	/** empuja las actualizaciones perezosas a los hijos de v */
	void push_down(int v, int l, int r) {
		int m = (l + r) / 2;
		apply(2 * v, m - l + 1, lazy[v]);
		apply(2 * v + 1, r - m, lazy[v]);
		lazy[v] = 0;
	}
 
	void range_add(int v, int l, int r, int ql, int qr, int add) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(v, r - l + 1, add);
		} else {
			push_down(v, l, r);
			int m = (l + r) / 2;
			range_add(2 * v, l, m, ql, qr, add);
			range_add(2 * v + 1, m + 1, r, ql, qr, add);
			tree[v] = tree[2 * v] + tree[2 * v + 1];
		}
	}
 
	T range_sum(int v, int l, int r, int ql, int qr) {
		if (qr < l || ql > r) { return 0; }
		if (ql <= l && r <= qr) { return tree[v]; }
		push_down(v, l, r);
		int m = (l + r) / 2;
		return range_sum(2 * v, l, m, ql, qr) + range_sum(2 * v + 1, m + 1, r, ql, qr);
	}
 
  public:
	LazySegtree(int n) : sz(n), tree(4 * n), lazy(4 * n) {}
 
	/** suma a cada valor del rango [ql, qr] */
	void range_add(int ql, int qr, int add) { range_add(1, 0, sz - 1, ql, qr, add); }
 
	/** @return suma de los valores de [ql, qr] */
	T range_sum(int ql, int qr) { return range_sum(1, 0, sz - 1, ql, qr); }
};
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, q;
		cin >> n >> q;
 
		LazySegtree<ll> st(n);
		for (int i = 0; i < q; i++) {
			int type;
			cin >> type;
 
			if (type == 0) {
				int p, q, val;
				cin >> p >> q >> val;
				p--, q--;
				st.range_add(p, q, val);
			} else {
				int p, q;
				cin >> p >> q;
				p--, q--;
				cout << st.range_sum(p, q) << '\n';
			}
		}
	}
}

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Range Updates & Sums	Fácil	Lazy SegTree	en el módulo

Explicación

Este problema pide soportar los siguientes tipos de consultas:

Sumar un valor a todos los elementos del rango $[a,b]$ .
Poner todos los valores del rango $[a,b]$ en un valor dado.
Hallar la suma de todos los valores del rango $[a,b]$ .

Considerar los dos primeros tipos de consultas. Se creará una etiqueta perezosa (lazy tag) en cada nodo del árbol para cada tipo. En esta solución, $\texttt{lzAdd}$ representará la etiqueta perezosa de la consulta de suma de rango y $\texttt{lzSet}$ representará la etiqueta perezosa de la consulta de asignación de rango.

Dados los dos tipos distintos de consultas de actualización, pueden ocurrir en total cuatro situaciones distintas después de cualquier actualización:

Suma de rango cuando $\texttt{lzSet}$ vale 0: simplemente sumar el valor nuevo al valor preexistente.
Suma de rango cuando $\texttt{lzSet}$ no vale 0: sumar el valor nuevo a $\texttt{lzSet}$ y limpiar $\texttt{lzAdd}$ .
Asignación de rango cuando $\texttt{lzAdd}$ vale 0: simplemente actualizar el valor de $\texttt{lzSet}$ .
Asignación de rango cuando $\texttt{lzAdd}$ no vale 0: de nuevo, simplemente actualizar el valor de $\texttt{lzSet}$ , porque una actualización de asignación pisa todas las actualizaciones de suma anteriores.

Dada la mecánica detrás de la función push_down, solo hace falta un árbol de segmentos de suma de rango habitual para resolver el problema.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
/**
 * Representa el tipo de actualización perezosa que se está haciendo.
 * NONE = si no hay actualización perezosa que realizar.
 */
enum QueryType { ADD, SET, NONE };
 
struct Query {
	QueryType type = NONE;
	ll val = 0;
};
 
template <typename T> class LazySegtree {
  private:
	const int sz;
	vector<T> tree;      // tree[i] = suma del rango de este nodo
	vector<Query> lazy;  // lazy[i] = actualización perezosa del rango
 
	/** construye los nodos del segtree */
	void build(int v, int l, int r, const vector<T> &a) {
		if (l == r) {
			tree[v] = a[l];
		} else {
			int m = (l + r) / 2;
			build(2 * v, l, m, a);
			build(2 * v + 1, m + 1, r, a);
			tree[v] = tree[2 * v] + tree[2 * v + 1];
		}
	}
 
	/** aplica la actualización perezosa a tree[v], la coloca en lazy[v] */
	void apply(int v, int len, const Query &x) {
		if (x.type == ADD) {
			// si el tipo de lazy[v] es NONE o ADD, entonces sumamos al
			// rango; si no, sumamos a nuestro valor de asignación perezosa
			if (lazy[v].type != SET) {
				lazy[v] = Query{ADD, lazy[v].val + x.val};
			} else {
				lazy[v] = Query{SET, lazy[v].val + x.val};
			}
			tree[v] += x.val * len;
		} else if (x.type == SET) {
			// la asignación perezosa pisa cualquier actualización previa
			tree[v] = x.val * len;
			lazy[v] = x;
		}
	}
 
	/** empuja la actualización perezosa a los hijos de v */
	void push_down(int v, int l, int r) {
		int m = (l + r) / 2;
		apply(2 * v, m - l + 1, lazy[v]);
		apply(2 * v + 1, r - m, lazy[v]);
		lazy[v] = Query();
	}
 
	void range_update(int v, int l, int r, int ql, int qr, const Query &x) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(v, r - l + 1, x);
		} else {
			push_down(v, l, r);
			int m = (l + r) / 2;
			range_update(2 * v, l, m, ql, qr, x);
			range_update(2 * v + 1, m + 1, r, ql, qr, x);
			tree[v] = tree[2 * v] + tree[2 * v + 1];
		}
	}
 
	T range_sum(int v, int l, int r, int ql, int qr) {
		if (qr < l || ql > r) { return 0; }
		if (l >= ql && r <= qr) { return tree[v]; }
		push_down(v, l, r);
		int m = (l + r) / 2;
		return range_sum(2 * v, l, m, ql, qr) + range_sum(2 * v + 1, m + 1, r, ql, qr);
	}
 
  public:
	LazySegtree(const vector<T> &a) : sz(a.size()), tree(4 * sz), lazy(4 * sz) {
		build(1, 0, sz - 1, a);
	}
 
	/** actualiza [ql, qr] con la actualización x */
	void range_update(int ql, int qr, const Query &x) {
		range_update(1, 0, sz - 1, ql, qr, x);
	}
 
	/** suma de los valores del arreglo en [ql, qr] */
	T range_sum(int ql, int qr) { return range_sum(1, 0, sz - 1, ql, qr); }
};
 
int main() {
	int n, q;
	cin >> n >> q;
	vector<ll> a(n);
	for (ll &i : a) { cin >> i; }
 
	LazySegtree<ll> st(a);
	for (int t = 0; t < q; t++) {
		int type, a, b;
		cin >> type >> a >> b;
		a--, b--;
		if (type == 1) {
			int x;
			cin >> x;
			st.range_update(a, b, Query{ADD, x});
		} else if (type == 2) {
			int x;
			cin >> x;
			st.range_update(a, b, Query{SET, x});
		} else {
			cout << st.range_sum(a, b) << '\n';
		}
	}
}

Los árboles de segmentos perezosos son notorios por ser difíciles de hacer genéricos. La plantilla de AtCoder es un ejemplo de una plantilla completamente genérica.

Abajo hay una implementación del problema foco usando una plantilla algo genérica. La idea es suministrar al template una clase Info y una clase Tag. La clase Tag maneja las actualizaciones perezosas, y cómo interactúan entre sí. Mientras tanto, la clase Info maneja los valores del árbol, y cómo se aplican las actualizaciones perezosas a esos valores.

Algunos detalles clave de implementación:

Hay que dar valores neutros a las etiquetas perezosas y a los valores del árbol. Es decir, hay que poner dentro de las clases algún valor que no afecte nuestras respuestas.
Para la función apply en las funciones de Info y Tag, hay que asegurarse de no aplicar actualizaciones neutras a ningún nodo.

C++


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
template <class Info, class Tag> class LazySegtree {
  private:
	const int n;
	vector<Info> tree;
	vector<Tag> lazy;
 
	/** construye los valores del segtree en tiempo O(N) */
	void build(int v, int l, int r, const vector<Info> &a) {
		if (l == r) {
			tree[v] = a[l];
		} else {
			int m = (l + r) / 2;
			build(2 * v, l, m, a);
			build(2 * v + 1, m + 1, r, a);
			tree[v] = tree[2 * v] + tree[2 * v + 1];
		}
	}
 
	/** aplica la actualización x a lazy[v] y tree[v] */
	void apply(int v, int l, int r, const Tag &x) {
		tree[v].apply(x, l, r);
		lazy[v].apply(x);
	}
 
	/** empuja las actualizaciones perezosas a los hijos de v */
	void push_down(int v, int l, int r) {
		int m = (l + r) / 2;
		apply(2 * v, l, m, lazy[v]);
		apply(2 * v + 1, m + 1, r, lazy[v]);
		lazy[v] = Tag();
	}
 
	void range_update(int v, int l, int r, int ql, int qr, const Tag &x) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(v, l, r, x);
		} else {
			push_down(v, l, r);
			int m = (l + r) / 2;
			range_update(2 * v, l, m, ql, qr, x);
			range_update(2 * v + 1, m + 1, r, ql, qr, x);
			tree[v] = tree[2 * v] + tree[2 * v + 1];
		}
	}
 
	Info range_query(int v, int l, int r, int ql, int qr) {
		if (qr < l || ql > r) { return Info(); }
		if (l >= ql && r <= qr) { return tree[v]; }
		push_down(v, l, r);
		int m = (l + r) / 2;
		return range_query(2 * v, l, m, ql, qr) +
		       range_query(2 * v + 1, m + 1, r, ql, qr);
	}
 
  public:
	LazySegtree() {}
 
	LazySegtree(int n) : n(n) {
		tree.assign(4 << __lg(n), Info());
		lazy.assign(4 << __lg(n), Tag());
	}
 
	LazySegtree(const vector<Info> &a) : n(a.size()) {
		tree.assign(4 << __lg(n), Info());
		lazy.assign(4 << __lg(n), Tag());
		build(1, 0, n - 1, a);
	}
 
	/** actualiza [ql, qr] con la actualización arbitraria elegida */
	void range_update(int ql, int qr, const Tag &x) {
		range_update(1, 0, n - 1, ql, qr, x);
	}
 
	/** @return resultado de la consulta de rango sobre [ql, qr] */
	Info range_query(int ql, int qr) { return range_query(1, 0, n - 1, ql, qr); }
};
 
enum QueryType { ADD, SET, NONE };
 
struct Tag {
	QueryType type = NONE;
	ll val = 0;
	void apply(const Tag &t) {
		if (t.type == ADD) {
			val += t.val;
			if (type != SET) { type = ADD; }
		} else if (t.type == SET) {
			type = SET;
			val = t.val;
		}
	}
};
 
struct Info {
	ll sum = 0;
	void apply(const Tag &t, int l, int r) {
		if (t.type == SET) {
			sum = t.val * (r - l + 1);
		} else if (t.type == ADD) {
			sum += t.val * (r - l + 1);
		}
	}
};
 
/** @return resultado de unir los nodos a y b */
Info operator+(const Info &a, const Info &b) { return {a.sum + b.sum}; }
 
int main() {
	int n, q;
	cin >> n >> q;
	vector<Info> a(n);
	for (Info &i : a) { cin >> i.sum; }
 
	LazySegtree<Info, Tag> st(a);
	for (int t = 0; t < q; t++) {
		int type, a, b;
		cin >> type >> a >> b;
		a--, b--;
		if (type == 1) {
			int x;
			cin >> x;
			st.range_update(a, b, Tag{ADD, x});
		} else if (type == 2) {
			int x;
			cin >> x;
			st.range_update(a, b, Tag{SET, x});
		} else {
			cout << st.range_query(a, b).sum << '\n';
		}
	}
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
YS	Range Affine Range Sum	Fácil	Lazy SegTree	Solución
Platinum	Counting Haybales	Fácil	Lazy SegTree	Solución
CSES	Prefix Sum Queries	Fácil	Lazy SegTree	Solución
Old Gold	The Lazy Cow	Fácil	Lazy SegTree	—
IOI	2014 - Wall	Normal	Lazy SegTree	Solución
IOI	2005 - Mountain	Normal	Lazy SegTree, Coordinate Compression	Solución
Platinum	Bessie's Snow Cow	Normal	Euler Tour, PURS, Lazy SegTree	Solución
CF	Diverging Directions	Normal	Euler Tour, RURQ	Solución
JOI	2018 - Bubble Sort 2	Muy difícil	Lazy SegTree	Solución
DMOPC	Victor Identifies Software	Muy difícil	Lazy SegTree	—