Árbol de Segmentos Beats

Árbol de Segmentos Beats

Solución - The Child and Sequence

Primero consideremos un Árbol de Segmentos perezoso. Un pseudocódigo de la función de actualización se ve más o menos así:

function update(upd_left, upd_right, upd_value, tree_node, tree_left, tree_right)
	if upd_right < tree_left or tree_right < upd_left
		return
	if upd_left ≤ tree_left and tree_right ≤ upd_right
		apply update
		return
	push lazy updates down

	let tree_mid = (tree_left + tree_right) / 2
	let left_child = 2 * tree_node
	let right_child = 2 * tree_node + 1
	update(upd_left, upd_right, upd_value, left_child, tree_left, tree_mid)
	update(upd_left, upd_right, upd_value, right_child, tree_mid + 1, tree_right)
	merge values from children

Al principio, este problema puede parecer un problema ordinario de Árbol de Segmentos perezoso, pero las actualizaciones de módulo en un rango impiden que las actualizaciones se apilen. Es decir, para un nodo dado, es difícil calcular cuál será el valor de la suma del nodo después de una actualización. Además, en el arreglo perezoso, el módulo, a diferencia de la suma, no satisface $x \mod a \mod b = x \mod (a + b)$ ni ninguna otra identidad simple. ¿Cómo sorteamos esto?

Resulta que podemos aprovechar una propiedad importante del módulo. El módulo o bien no afecta a un número, o lo disminuye en al menos la mitad de lo que era. Si el número en cuestión es $x$ y el módulo fue por $m$, entonces esto se puede demostrar por casos:

• Si $m > x$, entonces $x$ no se ve afectado por $m$
• Si $m \le x / 2$, entonces después de la operación de módulo $x$ debe ser estrictamente menor que $m$
• Si $x / 2 < m \leq x$, entonces $x \mod m = x - m$. Esto se reduce entonces al segundo caso.

Ignoremos las operaciones de tipo 3 por el momento. Por esta propiedad del módulo, un elemento con valor $a$ se disminuirá a lo sumo $\lceil \log a \rceil$ veces (aunque un número mayor de actualizaciones puede no afectar al elemento). Teniendo esto en cuenta, podemos modificar ligeramente la función de actualización de módulo para incorporar estas optimizaciones.

function update(upd_left, upd_right, upd_value, tree_node, tree_left, tree_right)
	let cur_max = the maximum element in [tree_left, tree_right]

	if upd_right < tree_left or tree_right < upd_left or cur_max < upd_value
		return
	if tree_left = tree_right
		apply update
		return

	let tree_mid = (tree_left + tree_right) / 2
	let left_child = 2 * tree_node
	let right_child = 2 * tree_node + 1
	update(upd_left, upd_right, upd_value, left_child, tree_left, tree_mid)
	update(upd_left, upd_right, upd_value, right_child, tree_mid + 1, tree_right)
	merge values from children

Nota: Como ya no hacemos actualizaciones de rango con propagación perezosa, no hay necesidad de una etiqueta perezosa.

Guardaremos \texttt{cur\\_max} en un arreglo separado como un valor separado (fusionable). Aunque es posible que una sola consulta procese $\mathcal{O}(n)$ nodos, sobre todas las consultas esto se amortiza a la complejidad temporal aceptable de $\mathcal{O}((n + q)\log a)$.

Consideremos agregar las operaciones de tipo 3. Aunque la implementación es relativamente directa (simplemente una actualización puntual en el Árbol de Segmentos), la demostración de complejidad de la sección anterior se cae porque los elementos se pueden aumentar de vuelta a su valor máximo.

Definimos la entropía del arreglo como $\sum_{k = 1}^n \lceil \log a_k \rceil$, o de forma equivalente, el número máximo de operaciones de módulo para disminuir el arreglo a su estado base de todos 0s. Observar que cada operación de actualización corre en $\mathcal{\Omega}(\log n)$, así que si no hay actualizaciones puntuales, la complejidad temporal es $\mathcal{O}(n \log a \log n)$. Cada actualización puntual incrementa la entropía en una cantidad fija $\lceil \log a \rceil$. Si hay $q_p$ actualizaciones puntuales, entonces la entropía total sobre todas las actualizaciones está acotada por $n \log a + q_p \log a$. Si factorizamos estas operaciones de actualización puntual, cada actualización de módulo sigue estando acotada por la entropía total. Esto significa que incluso con actualizaciones puntuales, nuestra solución todavía corre en $\mathcal{O}(n \log a \log n + q_p \log a) = \mathcal{O}((n + q)\log n \log a)$.

Aunque estrictamente hablando, The Child and Sequence no es un problema de Árbol de Segmentos Beats, las técnicas usadas en él están estrechamente relacionadas. En resumen, el Árbol de Segmentos Beats es una técnica que permite una complejidad de actualización de rango no polilogarítmica que se amortiza a $\mathcal{O}(n \log n)$ o $\mathcal{O}(n \log^2 n)$.

Implementación - The Child and Sequence

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 100001;
 
int N, Q;
long long tsum[MAXN * 4], tmax[MAXN * 4];
 
void update_mod(int l, int r, long long v, int t = 1, int tl = 1, int tr = N) {
	if (r < tl || tr < l || tmax[t] < v) {
		return;
	} else if (tl == tr) {
		int val = tmax[t] % v;
		tsum[t] = tmax[t] = val;
		return;
	}
 
	int tm = (tl + tr) / 2;
	update_mod(l, r, v, t * 2, tl, tm);
	update_mod(l, r, v, t * 2 + 1, tm + 1, tr);
	tsum[t] = tsum[t * 2] + tsum[t * 2 + 1];
	tmax[t] = max(tmax[t * 2], tmax[t * 2 + 1]);
}
 
void update_set(int i, long long v, int t = 1, int tl = 1, int tr = N) {
	if (tl == tr) {
		tsum[t] = tmax[t] = v;
		return;
	}
 
	int tm = (tl + tr) / 2;
	if (i <= tm) {
		update_set(i, v, t * 2, tl, tm);
	} else {
		update_set(i, v, t * 2 + 1, tm + 1, tr);
	}
	tsum[t] = tsum[t * 2] + tsum[t * 2 + 1];
	tmax[t] = max(tmax[t * 2], tmax[t * 2 + 1]);
}
 
long long query(int l, int r, int t = 1, int tl = 1, int tr = N) {
	if (r < tl || tr < l) {
		return 0;
	} else if (l <= tl && tr <= r) {
		return tsum[t];
	}
 
	int tm = (tl + tr) / 2;
	return query(l, r, t * 2, tl, tm) + query(l, r, t * 2 + 1, tm + 1, tr);
}
 
int main() {
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		long long a;
		cin >> a;
		update_set(i, a);
	}
	for (int q = 0; q < Q; q++) {
		int t;
		cin >> t;
		if (t == 1) {
			int l, r;
			cin >> l >> r;
			cout << query(l, r) << '\n';
		} else if (t == 2) {
			int l, r;
			long long x;
			cin >> l >> r >> x;
			update_mod(l, r, x);
		} else if (t == 3) {
			int i;
			long long x;
			cin >> i >> x;
			update_set(i, x);
		}
	}
}

Solución - Range Chmin Chmax Add Set Sum

La solución de The Child and Sequence usa una solución simplificada pero similar al Árbol de Segmentos Beats. Para el problema de arriba, dividámoslo en tres subtareas:

1. Permitir solo las operaciones 0 y 3
2. Permitir solo las operaciones 0, 2 y 3
3. Todas las operaciones están permitidas

Subtarea 1

Construimos un Árbol de Segmentos sobre el rango. En cada nodo del árbol, mantenemos cuatro valores: $\texttt{sum}$, $\texttt{max}_1$, $\texttt{max}_2$ y $\texttt{max}_c$, que corresponden respectivamente a la suma de los elementos de dicho rango, el valor máximo estricto, el segundo mayor valor estricto (si no hay tal valor, $-\infty$), y el número de ocurrencias del elemento máximo. Quisiéramos realizar las siguientes operaciones:

• Para cada $i \in [l, r]$, sea $A[i] = \min(A[i], x)$ (esta operación se denominará de aquí en más chmin)
• Consultar $\sum_{i = l}^r A[i]$

El problema, de nuevo, es que en la propagación perezosa es difícil actualizar la suma para reflejar la actualización chmin. Usaremos una estrategia similar a la de la tarea anterior donde construimos una solución aparentemente lenta y luego la optimizamos para que pase en tiempo.

Primero, si el valor de actualización es mayor que el valor máximo del rango (guardado en $\texttt{max}_1$), entonces podemos retornar ya que la actualización no afectará a ningún elemento del rango. Segundo, si el valor de actualización está entre $\texttt{max}_1$ y $\texttt{max}_2$, la nueva suma se puede calcular fácilmente usando $\texttt{max}_c$.

function update(upd_left, upd_right, upd_value, tree_node, tree_left, tree_right)
	if upd_right < tree_left or tree_right < upd_left or max1 < upd_value
		return
	if upd_left < tree_left and tree_right < upd_right and max2 < upd_value
		apply update
		return
	push lazy updates down

	let tree_mid = (tree_left + tree_right) / 2
	let left_child = 2 * tree_node
	let right_child = 2 * tree_node + 1
	update(upd_left, upd_right, upd_value, left_child, tree_left, tree_mid)
	update(upd_left, upd_right, upd_value, right_child, tree_mid + 1, tree_right)
	merge values from children

Para demostrar que esto corre en $\mathcal{O}((n + q) \log n)$, necesitamos definir una variable $\delta$ que representa la suma del número de elementos distintos sobre todos los intervalos del Árbol de Segmentos. Este número está acotado por $n \log n$, que es la suma de los tamaños de cada intervalo.

¿Por qué las consultas son lentas? Porque podrían visitar hasta $n$ nodos en cualquier consulta dada. Definimos una operación extra como cuando una consulta se pasa a los hijos de un nodo a pesar de estar en el rango de la consulta. En otras palabras, cuando un nodo cumple query_left ≤ tree_left and tree_right ≤ query_right and upd_value ≤ max2, se realiza una operación extra.

Cada vez que se realiza una operación extra, $\delta$ disminuye en al menos 1, porque tanto los elementos $\texttt{max}_1$ como $\texttt{max}_2$ se disminuyen a $x$. Como $\delta$ no aumenta, la complejidad está acotada por $\max \delta = \mathcal{O}(n \log n)$.

Subtarea 2

Las actualizaciones de suma en un rango se pueden agregar sin mucha modificación al código existente, simplemente agregando otra etiqueta perezosa. La demostración de la complejidad temporal de la parte anterior se cae, pero una cota superior tentativa del algoritmo es $\mathcal{O}((n + q) \log^2 n)$. Una demostración completa se puede encontrar aquí .

Subtarea 3

Guardamos tres variables más $\texttt{min}_1$, $\texttt{min}_2$ y $\texttt{min}_c$. Estas se implementarán de forma similar a sus contrapartes $\texttt{max}$. Hay que tener en cuenta el caso borde cuando $\texttt{min}_1 = \texttt{max}_2$ o viceversa.

Implementación - Range Chmin Chmax Add Range Sum

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int MAXN = 200001;  // 1-based
 
int N;
ll A[MAXN];
 
struct Node {
	ll sum;   // Sum tag
	ll max1;  // Max value
	ll max2;  // Second Max value
	ll maxc;  // Max value count
	ll min1;  // Min value
	ll min2;  // Second Min value
	ll minc;  // Min value count
	ll lazy;  // Lazy tag
} T[MAXN * 4];
 
void merge(int t) {
	// sum
	T[t].sum = T[t << 1].sum + T[t << 1 | 1].sum;
 
	// max
	if (T[t << 1].max1 == T[t << 1 | 1].max1) {
		T[t].max1 = T[t << 1].max1;
		T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max2);
		T[t].maxc = T[t << 1].maxc + T[t << 1 | 1].maxc;
	} else {
		if (T[t << 1].max1 > T[t << 1 | 1].max1) {
			T[t].max1 = T[t << 1].max1;
			T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max1);
			T[t].maxc = T[t << 1].maxc;
		} else {
			T[t].max1 = T[t << 1 | 1].max1;
			T[t].max2 = max(T[t << 1].max1, T[t << 1 | 1].max2);
			T[t].maxc = T[t << 1 | 1].maxc;
		}
	}
 
	// min
	if (T[t << 1].min1 == T[t << 1 | 1].min1) {
		T[t].min1 = T[t << 1].min1;
		T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min2);
		T[t].minc = T[t << 1].minc + T[t << 1 | 1].minc;
	} else {
		if (T[t << 1].min1 < T[t << 1 | 1].min1) {
			T[t].min1 = T[t << 1].min1;
			T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min1);
			T[t].minc = T[t << 1].minc;
		} else {
			T[t].min1 = T[t << 1 | 1].min1;
			T[t].min2 = min(T[t << 1].min1, T[t << 1 | 1].min2);
			T[t].minc = T[t << 1 | 1].minc;
		}
	}
}
 
void push_add(int t, int tl, int tr, ll v) {
	if (v == 0) { return; }
	T[t].sum += (tr - tl + 1) * v;
	T[t].max1 += v;
	if (T[t].max2 != -llINF) { T[t].max2 += v; }
	T[t].min1 += v;
	if (T[t].min2 != llINF) { T[t].min2 += v; }
	T[t].lazy += v;
}
 
// corresponds to a chmin update
void push_max(int t, ll v, bool l) {
	if (v >= T[t].max1) { return; }
	T[t].sum -= T[t].max1 * T[t].maxc;
	T[t].max1 = v;
	T[t].sum += T[t].max1 * T[t].maxc;
	if (l) {
		T[t].min1 = T[t].max1;
	} else {
		if (v <= T[t].min1) {
			T[t].min1 = v;
		} else if (v < T[t].min2) {
			T[t].min2 = v;
		}
	}
}
 
// corresponds to a chmax update
void push_min(int t, ll v, bool l) {
	if (v <= T[t].min1) { return; }
	T[t].sum -= T[t].min1 * T[t].minc;
	T[t].min1 = v;
	T[t].sum += T[t].min1 * T[t].minc;
	if (l) {
		T[t].max1 = T[t].min1;
	} else {
		if (v >= T[t].max1) {
			T[t].max1 = v;
		} else if (v > T[t].max2) {
			T[t].max2 = v;
		}
	}
}
 
void pushdown(int t, int tl, int tr) {
	if (tl == tr) return;
	// sum
	int tm = (tl + tr) >> 1;
	push_add(t << 1, tl, tm, T[t].lazy);
	push_add(t << 1 | 1, tm + 1, tr, T[t].lazy);
	T[t].lazy = 0;
 
	// max
	push_max(t << 1, T[t].max1, tl == tm);
	push_max(t << 1 | 1, T[t].max1, tm + 1 == tr);
 
	// min
	push_min(t << 1, T[t].min1, tl == tm);
	push_min(t << 1 | 1, T[t].min1, tm + 1 == tr);
}
 
void build(int t = 1, int tl = 0, int tr = N - 1) {
	T[t].lazy = 0;
	if (tl == tr) {
		T[t].sum = T[t].max1 = T[t].min1 = A[tl];
		T[t].maxc = T[t].minc = 1;
		T[t].max2 = -llINF;
		T[t].min2 = llINF;
		return;
	}
 
	int tm = (tl + tr) >> 1;
	build(t << 1, tl, tm);
	build(t << 1 | 1, tm + 1, tr);
	merge(t);
}
 
void update_add(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return; }
	if (l <= tl && tr <= r) {
		push_add(t, tl, tr, v);
		return;
	}
	pushdown(t, tl, tr);
 
	int tm = (tl + tr) >> 1;
	update_add(l, r, v, t << 1, tl, tm);
	update_add(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}
 
void update_chmin(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l || v >= T[t].max1) { return; }
	if (l <= tl && tr <= r && v > T[t].max2) {
		push_max(t, v, tl == tr);
		return;
	}
	pushdown(t, tl, tr);
 
	int tm = (tl + tr) >> 1;
	update_chmin(l, r, v, t << 1, tl, tm);
	update_chmin(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}
 
void update_chmax(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l || v <= T[t].min1) { return; }
	if (l <= tl && tr <= r && v < T[t].min2) {
		push_min(t, v, tl == tr);
		return;
	}
	pushdown(t, tl, tr);
 
	int tm = (tl + tr) >> 1;
	update_chmax(l, r, v, t << 1, tl, tm);
	update_chmax(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}
 
ll query_sum(int l, int r, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return 0; }
	if (l <= tl && tr <= r) { return T[t].sum; }
	pushdown(t, tl, tr);
 
	int tm = (tl + tr) >> 1;
	return query_sum(l, r, t << 1, tl, tm) + query_sum(l, r, t << 1 | 1, tm + 1, tr);
}
 
int main() {
	int Q;
 
	cin >> N >> Q;
	for (int i = 0; i < N; i++) { cin >> A[i]; }
	build();
	for (int q = 0; q < Q; q++) {
		int t;
		cin >> t;
		if (t == 0) {
			int l, r;
			ll x;
			cin >> l >> r >> x;
			update_chmin(l, r - 1, x);
		} else if (t == 1) {
			int l, r;
			ll x;
			cin >> l >> r >> x;
			update_chmax(l, r - 1, x);
		} else if (t == 2) {
			int l, r;
			ll x;
			cin >> l >> r >> x;
			update_add(l, r - 1, x);
		} else if (t == 3) {
			int l, r;
			cin >> l >> r;
			cout << query_sum(l, r - 1) << '\n';
		}
	}
}

Problemas