Árbol Sqrt

Dado un arreglo $a$ que contiene $n$ elementos y la operación $\circ$ que satisface la propiedad asociativa: $(x \circ y) \circ z = x \circ (y \circ z)$ es cierta para cualquier $x$ , $y$ , $z$ .

Así, operaciones como $\gcd$ , $\min$ , $\max$ , $+$ , $\text{and}$ , $\text{or}$ , $\text{xor}$ , etc. satisfacen estas condiciones.

También tenemos algunas consultas $q(l, r)$ . Para cada consulta, hay que calcular $a_l \circ a_{l+1} \circ \dots \circ a_r$ .

El Árbol Sqrt (Sqrt Tree) puede procesar tales consultas en tiempo $O(1)$ con tiempo de preprocesamiento $O(n \cdot \log \log n)$ y memoria $O(n \cdot \log \log n)$ .

Descripción

Construir la descomposición por raíz cuadrada

Hagamos una descomposición por raíz cuadrada. Dividimos nuestro arreglo en $\sqrt{n}$ bloques, cada bloque tiene tamaño $\sqrt{n}$ . Para cada bloque, calculamos:

Respuestas a las consultas que yacen en el bloque y empiezan al principio del bloque ( $\text{prefixOp}$ )
Respuestas a las consultas que yacen en el bloque y terminan al final del bloque ( $\text{suffixOp}$ )

Y calcularemos un arreglo adicional:

$\text{between}_{i, j}$ (para $i \le j$ ) — respuesta a la consulta que empieza al inicio del bloque $i$ y termina al final del bloque $j$ . Nótese que tenemos $\sqrt{n}$ bloques, así que el tamaño de este arreglo será $O(\sqrt{n}^2) = O(n)$ .

Veamos el ejemplo.

Sea $\circ$ igual a $+$ (calculamos la suma en un segmento) y tenemos el siguiente arreglo $a$ :

{1, 2, 3, 4, 5, 6, 7, 8, 9}

Se dividirá en tres bloques: {1, 2, 3}, {4, 5, 6} y {7, 8, 9}.

Para el primer bloque $\text{prefixOp}$ es {1, 3, 6} y $\text{suffixOp}$ es {6, 5, 3}.

Para el segundo bloque $\text{prefixOp}$ es {4, 9, 15} y $\text{suffixOp}$ es {15, 11, 6}.

Para el tercer bloque $\text{prefixOp}$ es {7, 15, 24} y $\text{suffixOp}$ es {24, 17, 9}.

El arreglo $\text{between}$ es:


{
    {6, 21, 45},
    {0, 15, 39},
    {0, 0,  24}
}

(asumimos que los elementos inválidos donde $i > j$ se rellenan con ceros)

Es obvio ver que estos arreglos se pueden calcular fácilmente en tiempo y memoria $O(n)$ .

Ya podemos responder algunas consultas usando estos arreglos. Si la consulta no cabe en un solo bloque, podemos partirla en tres partes: sufijo de un bloque, luego algún segmento de bloques contiguos y luego prefijo de algún bloque. Podemos responder una consulta partiéndola en tres partes y aplicando nuestra operación a algún valor de $\text{suffixOp}$ , luego algún valor de $\text{between}$ , luego algún valor de $\text{prefixOp}$ .

Pero si tenemos consultas que caben por completo en un solo bloque, no podemos procesarlas usando estos tres arreglos. Así que hay que hacer algo.

Hacer un árbol

No podemos responder solo las consultas que caben por completo en un bloque. ¿Pero qué si construimos la misma estructura descrita arriba para cada bloque? Sí, podemos hacerlo. Y lo hacemos de forma recursiva, hasta alcanzar el tamaño de bloque de $1$ o $2$ . Las respuestas para tales bloques se pueden calcular fácilmente en $O(1)$ .

Así, obtenemos un árbol. Cada nodo del árbol representa algún segmento del arreglo. Un nodo que representa un segmento del arreglo de tamaño $k$ tiene $\sqrt{k}$ hijos — uno por cada bloque. Además cada nodo contiene los tres arreglos descritos arriba para el segmento que contiene. La raíz del árbol representa todo el arreglo. Los nodos con longitudes de segmento $1$ o $2$ son hojas.

También es obvio que la altura de este árbol es $O(\log \log n)$ , porque si algún vértice del árbol representa un arreglo de longitud $k$ , entonces sus hijos tienen longitud $\sqrt{k}$ . $\log(\sqrt{k}) = \frac{\log{k}}{2}$ , así que $\log k$ disminuye a la mitad en cada capa del árbol y por tanto su altura es $O(\log \log n)$ . El tiempo de construcción y el uso de memoria serán $O(n \cdot \log \log n)$ , porque cada elemento del arreglo aparece exactamente una vez en cada capa del árbol.

Ahora podemos responder las consultas en $O(\log \log n)$ . Podemos bajar por el árbol hasta encontrar un segmento de longitud $1$ o $2$ (la respuesta para él se puede calcular en tiempo $O(1)$ ) o encontrar el primer segmento en el que nuestra consulta no cabe por completo en un solo bloque. Véase la primera sección sobre cómo responder la consulta en este caso.

Bien, ahora podemos hacer $O(\log \log n)$ por consulta. ¿Se puede hacer más rápido?

Optimizar la complejidad de la consulta

Una de las optimizaciones más obvias es hacer búsqueda binaria del nodo del árbol que necesitamos. Usando búsqueda binaria, podemos alcanzar la complejidad $O(\log \log \log n)$ por consulta. ¿Podemos hacerlo aún más rápido?

La respuesta es sí. Asumamos las siguientes dos cosas:

Cada tamaño de bloque es una potencia de dos.
Todos los bloques son iguales en cada capa.

Para lograr esto, podemos agregar algunos elementos cero a nuestro arreglo de modo que su tamaño se vuelva una potencia de dos.

Cuando usamos esto, algunos tamaños de bloque pueden volverse el doble de grandes para ser una potencia de dos, pero seguirán siendo $O(\sqrt{k})$ en tamaño y mantenemos complejidad lineal para construir los arreglos en un segmento.

Ahora, podemos comprobar fácilmente si la consulta cabe por completo en un bloque de tamaño $2^k$ . Escribamos los rangos de la consulta, $l$ y $r$ (usamos indexación desde cero) en forma binaria. Por ejemplo, asumamos $k=4, l=39, r=46$ . La representación binaria de $l$ y $r$ es:

$l = 39_{10} = 100111_2$

$r = 46_{10} = 101110_2$

Recordemos que una capa contiene segmentos del mismo tamaño, y los bloques en una capa también tienen el mismo tamaño (en nuestro caso, su tamaño es $2^k = 2^4 = 16$ . Los bloques cubren el arreglo por completo, así que el primer bloque cubre los elementos $(0 - 15)$ ( $(000000_2 - 001111_2)$ en binario), el segundo cubre los elementos $(16 - 31)$ ( $(010000_2 - 011111_2)$ en binario) y así sucesivamente. Vemos que los índices de las posiciones cubiertas por un bloque pueden diferir solo en los $k$ (en nuestro caso, $4$ ) últimos bits. En nuestro caso $l$ y $r$ tienen bits iguales excepto los cuatro más bajos, así que yacen en un mismo bloque.

Así, hay que comprobar si no difieren más que los $k$ bits más pequeños (o $l\ \text{xor}\ r$ no excede $2^k-1$ ).

Usando esta observación, podemos encontrar una capa que sea adecuada para responder la consulta de forma rápida. Cómo hacerlo:

Para cada $i$ que no exceda el tamaño del arreglo, encontramos el bit más alto que es igual a $1$ . Para hacerlo rápido, usamos DP y un arreglo precalculado.
Ahora, para cada $q(l, r)$ encontramos el bit más alto de $l\ \text{xor}\ r$ y, usando esta información, es fácil elegir la capa en la que podemos procesar la consulta fácilmente. También podemos usar un arreglo precalculado aquí.

Para más detalles, véase el código de abajo.

Así, usando esto, podemos responder las consultas en $O(1)$ cada una. ¡Hurra! :)

Actualizar elementos

También podemos actualizar elementos en el Árbol Sqrt. Se soportan tanto actualizaciones de un solo elemento como actualizaciones sobre un segmento.

Actualizar un solo elemento

Consideremos una consulta $\text{update}(x, val)$ que hace la asignación $a_x = val$ . Hay que realizar esta consulta lo bastante rápido.

Enfoque naive

Primero, veamos qué cambia en el árbol cuando cambia un solo elemento. Consideremos un nodo del árbol de longitud $l$ y sus arreglos: $\text{prefixOp}$ , $\text{suffixOp}$ y $\text{between}$ . Es fácil ver que solo cambian $O(\sqrt{l})$ elementos de $\text{prefixOp}$ y $\text{suffixOp}$ (solo dentro del bloque con el elemento cambiado). Se cambian $O(l)$ elementos en $\text{between}$ . Por lo tanto, se actualizan $O(l)$ elementos en el nodo del árbol.

Recordamos que cualquier elemento $x$ está presente en exactamente un nodo del árbol en cada capa. El nodo raíz (capa $0$ ) tiene longitud $O(n)$ , los nodos en la capa $1$ tienen longitud $O(\sqrt{n})$ , los nodos en la capa $2$ tienen longitud $O(\sqrt{\sqrt{n}})$ , etc. Así que la complejidad temporal por actualización es $O(n + \sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(n)$ .

Pero es demasiado lento. ¿Se puede hacer más rápido?

Un Árbol Sqrt dentro del Árbol Sqrt

Nótese que el cuello de botella de la actualización es reconstruir $\text{between}$ del nodo raíz. Para optimizar el árbol, ¡deshagámonos de este arreglo! En lugar del arreglo $\text{between}$ , guardamos otro Árbol Sqrt para el nodo raíz. Llamémoslo $\text{index}$ . Juega el mismo papel que $\text{between}$ : responde las consultas sobre segmentos de bloques. Nótese que el resto de los nodos del árbol no tienen $\text{index}$ , mantienen sus arreglos $\text{between}$ .

Un Árbol Sqrt está indexado si su nodo raíz tiene $\text{index}$ . Un Árbol Sqrt con arreglo $\text{between}$ en su nodo raíz está no indexado. Nótese que $\text{index}$ está no indexado él mismo.

Así, tenemos el siguiente algoritmo para actualizar un árbol indexado:

Actualizar $\text{prefixOp}$ y $\text{suffixOp}$ en $O(\sqrt{n})$ .
Actualizar $\text{index}$ . Tiene longitud $O(\sqrt{n})$ y hay que actualizar solo un ítem en él (el que representa el bloque cambiado). Así, la complejidad temporal de este paso es $O(\sqrt{n})$ . Podemos usar el algoritmo descrito al principio de esta sección (el “lento”) para hacerlo.
Ir al nodo hijo que representa el bloque cambiado y actualizarlo en $O(\sqrt{n})$ con el algoritmo “lento”.

Nótese que la complejidad de la consulta sigue siendo $O(1)$ : hay que usar $\text{index}$ en la consulta no más de una vez, y esto tomará tiempo $O(1)$ .

Así, la complejidad temporal total para actualizar un solo elemento es $O(\sqrt{n})$ . ¡Hurra! :)

Actualizar un segmento

El Árbol Sqrt también puede hacer cosas como asignar un elemento sobre un segmento. $\text{massUpdate}(x, l, r)$ significa $a_i = x$ para todo $l \le i \le r$ .

Hay dos enfoques para hacer esto: uno de ellos hace $\text{massUpdate}$ en $O(\sqrt{n}\cdot \log \log n)$ , manteniendo $O(1)$ por consulta. El segundo hace $\text{massUpdate}$ en $O(\sqrt{n})$ , pero la complejidad de la consulta se vuelve $O(\log \log n)$ .

Haremos propagación perezosa de la misma forma que se hace en los Árboles de Segmentos: marcamos algunos nodos como lazy, lo que significa que los empujaremos cuando sea necesario. Pero una cosa es distinta de los Árboles de Segmentos: empujar un nodo es caro, así que no se puede hacer en las consultas. En la capa $0$ , empujar un nodo toma tiempo $O(\sqrt{n})$ . Así, no empujamos nodos dentro de las consultas, solo miramos si el nodo actual o su padre están lazy, y simplemente lo tenemos en cuenta al realizar las consultas.

Primer enfoque

En el primer enfoque, decimos que solo los nodos de la capa $1$ (con longitud $O(\sqrt{n}$ ) pueden ser lazy. Al empujar tal nodo, actualiza todo su subárbol incluyéndose a sí mismo en $O(\sqrt{n}\cdot \log \log n)$ . El proceso $\text{massUpdate}$ se hace de la siguiente forma:

Considerar los nodos de la capa $1$ y los bloques correspondientes a ellos.
Algunos bloques están cubiertos por completo por $\text{massUpdate}$ . Marcarlos como lazy en $O(\sqrt{n})$ .
Algunos bloques están cubiertos de forma parcial. Nótese que no hay más de dos bloques de este tipo. Reconstruirlos en $O(\sqrt{n}\cdot \log \log n)$ . Si estaban lazy, tenerlo en cuenta.
Actualizar $\text{prefixOp}$ y $\text{suffixOp}$ para los bloques cubiertos de forma parcial en $O(\sqrt{n})$ (porque solo hay dos bloques de ese tipo).
Reconstruir el $\text{index}$ en $O(\sqrt{n}\cdot \log \log n)$ .

Así podemos hacer $\text{massUpdate}$ de forma rápida. ¿Pero cómo afecta la propagación perezosa a las consultas? Tendrán las siguientes modificaciones:

Si nuestra consulta yace por completo en un bloque lazy, calcularla y tener en cuenta lazy. $O(1)$ .
Si nuestra consulta consiste de muchos bloques, algunos de los cuales son lazy, hay que ocuparse de lazy solo en el bloque más a la izquierda y el más a la derecha. El resto de los bloques se calculan usando $\text{index}$ , que ya conoce la respuesta sobre el bloque lazy (porque se reconstruye después de cada modificación). $O(1)$ .

La complejidad de la consulta sigue siendo $O(1)$ .

Segundo enfoque

En este enfoque, cada nodo puede ser lazy (excepto la raíz). Incluso los nodos en $\text{index}$ pueden ser lazy. Así, al procesar una consulta, tenemos que buscar etiquetas lazy en todos los nodos padre, es decir, la complejidad de la consulta será $O(\log \log n)$ .

Pero $\text{massUpdate}$ se vuelve más rápido. Se ve de la siguiente forma:

Algunos bloques están cubiertos por completo con $\text{massUpdate}$ . Así, se les agregan etiquetas lazy. Es $O(\sqrt{n})$ .
Actualizar $\text{prefixOp}$ y $\text{suffixOp}$ para los bloques cubiertos de forma parcial en $O(\sqrt{n})$ (porque solo hay dos bloques de ese tipo).
No olvidar actualizar el índice. Es $O(\sqrt{n})$ (usamos el mismo algoritmo $\text{massUpdate}$ ).
Actualizar el arreglo $\text{between}$ para los subárboles no indexados.
Ir a los nodos que representan los bloques cubiertos de forma parcial y llamar a $\text{massUpdate}$ de forma recursiva.

Nótese que cuando hacemos la llamada recursiva, hacemos $\text{massUpdate}$ de prefijo o de sufijo. Pero para actualizaciones de prefijo y de sufijo no podemos tener más de un hijo cubierto de forma parcial. Así, visitamos un nodo en la capa $1$ , dos nodos en la capa $2$ y dos nodos en cualquier nivel más profundo. Así, la complejidad temporal es $O(\sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(\sqrt{n})$ . El enfoque aquí es similar a la actualización masiva del Árbol de Segmentos.

Implementación

La siguiente implementación del Árbol Sqrt puede realizar las siguientes operaciones: construir en $O(n \cdot \log \log n)$ , responder consultas en $O(1)$ y actualizar un elemento en $O(\sqrt{n})$ .


SqrtTreeItem op(const SqrtTreeItem &a, const SqrtTreeItem &b);
 
inline int log2Up(int n) {
	int res = 0;
	while ((1 << res) < n) {
		res++;
	}
	return res;
}
 
class SqrtTree {
private:
	int n, lg, indexSz;
	vector<SqrtTreeItem> v;
	vector<int> clz, layers, onLayer;
	vector< vector<SqrtTreeItem> > pref, suf, between;
	
	inline void buildBlock(int layer, int l, int r) {
		pref[layer][l] = v[l];
		for (int i = l+1; i < r; i++) {
			pref[layer][i] = op(pref[layer][i-1], v[i]);
		}
		suf[layer][r-1] = v[r-1];
		for (int i = r-2; i >= l; i--) {
			suf[layer][i] = op(v[i], suf[layer][i+1]);
		}
	}
	
	inline void buildBetween(int layer, int lBound, int rBound, int betweenOffs) {
		int bSzLog = (layers[layer]+1) >> 1;
		int bCntLog = layers[layer] >> 1;
		int bSz = 1 << bSzLog;
		int bCnt = (rBound - lBound + bSz - 1) >> bSzLog;
		for (int i = 0; i < bCnt; i++) {
			SqrtTreeItem ans;
			for (int j = i; j < bCnt; j++) {
				SqrtTreeItem add = suf[layer][lBound + (j << bSzLog)];
				ans = (i == j) ? add : op(ans, add);
				between[layer-1][betweenOffs + lBound + (i << bCntLog) + j] = ans;
			}
		}
	}
	
	inline void buildBetweenZero() {
		int bSzLog = (lg+1) >> 1;
		for (int i = 0; i < indexSz; i++) {
			v[n+i] = suf[0][i << bSzLog];
		}
		build(1, n, n + indexSz, (1 << lg) - n);
	}
	
	inline void updateBetweenZero(int bid) {
		int bSzLog = (lg+1) >> 1;
		v[n+bid] = suf[0][bid << bSzLog];
		update(1, n, n + indexSz, (1 << lg) - n, n+bid);
	}
	
	void build(int layer, int lBound, int rBound, int betweenOffs) {
		if (layer >= (int)layers.size()) {
			return;
		}
		int bSz = 1 << ((layers[layer]+1) >> 1);
		for (int l = lBound; l < rBound; l += bSz) {
			int r = min(l + bSz, rBound);
			buildBlock(layer, l, r);
			build(layer+1, l, r, betweenOffs);
		}
		if (layer == 0) {
			buildBetweenZero();
		} else {
			buildBetween(layer, lBound, rBound, betweenOffs);
		}
	}
	
	void update(int layer, int lBound, int rBound, int betweenOffs, int x) {
		if (layer >= (int)layers.size()) {
			return;
		}
		int bSzLog = (layers[layer]+1) >> 1;
		int bSz = 1 << bSzLog;
		int blockIdx = (x - lBound) >> bSzLog;
		int l = lBound + (blockIdx << bSzLog);
		int r = min(l + bSz, rBound);
		buildBlock(layer, l, r);
		if (layer == 0) {
			updateBetweenZero(blockIdx);
		} else {
			buildBetween(layer, lBound, rBound, betweenOffs);
		}
		update(layer+1, l, r, betweenOffs, x);
	}
	
	inline SqrtTreeItem query(int l, int r, int betweenOffs, int base) {
		if (l == r) {
			return v[l];
		}
		if (l + 1 == r) {
			return op(v[l], v[r]);
		}
		int layer = onLayer[clz[(l - base) ^ (r - base)]];
		int bSzLog = (layers[layer]+1) >> 1;
		int bCntLog = layers[layer] >> 1;
		int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base;
		int lBlock = ((l - lBound) >> bSzLog) + 1;
		int rBlock = ((r - lBound) >> bSzLog) - 1;
		SqrtTreeItem ans = suf[layer][l];
		if (lBlock <= rBlock) {
			SqrtTreeItem add = (layer == 0) ? (
				query(n + lBlock, n + rBlock, (1 << lg) - n, n)
			) : (
				between[layer-1][betweenOffs + lBound + (lBlock << bCntLog) + rBlock]
			);
			ans = op(ans, add);
		}
		ans = op(ans, pref[layer][r]);
		return ans;
	}
public:
	inline SqrtTreeItem query(int l, int r) {
		return query(l, r, 0, 0);
	}
	
	inline void update(int x, const SqrtTreeItem &item) {
		v[x] = item;
		update(0, 0, n, 0, x);
	}
	
	SqrtTree(const vector<SqrtTreeItem>& a)
		: n((int)a.size()), lg(log2Up(n)), v(a), clz(1 << lg), onLayer(lg+1) {
		clz[0] = 0;
		for (int i = 1; i < (int)clz.size(); i++) {
			clz[i] = clz[i >> 1] + 1;
		}
		int tlg = lg;
		while (tlg > 1) {
			onLayer[tlg] = (int)layers.size();
			layers.push_back(tlg);
			tlg = (tlg+1) >> 1;
		}
		for (int i = lg-1; i >= 0; i--) {
			onLayer[i] = max(onLayer[i], onLayer[i+1]);
		}
		int betweenLayers = max(0, (int)layers.size() - 1);
		int bSzLog = (lg+1) >> 1;
		int bSz = 1 << bSzLog;
		indexSz = (n + bSz - 1) >> bSzLog;
		v.resize(n + indexSz);
		pref.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
		suf.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
		between.assign(betweenLayers, vector<SqrtTreeItem>((1 << lg) + bSz));
		build(0, 0, n, 0);
	}
};

Problemas

CodeChef - SEGPROD