Descomposición por raíz cuadrada

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Dynamic Range Sum Queries	Muy fácil	Sqrt	en el módulo

Este problema ya se debería haber hecho en Actualización puntual y suma de rango, pero aquí presentaremos dos enfoques más. Ambos corren en tiempo $\mathcal{O}(Q\sqrt N)$ .

Recursos
Fuente	Recurso	Notas
CPH	27 - Square Root Algorithms
CF	Applications of Square Root Decomposition	Bloques, algoritmo de Mo

Bloques

Partimos el arreglo en bloques de tamaño $\texttt{block\\_size}=\lceil \sqrt{N} \rceil$ . Cada bloque almacena la suma de los elementos que contiene, y permite crear las operaciones correspondientes de update y query.

Consultas de actualización: $\mathcal{O}(1)$

Para actualizar un elemento en la posición $x$ , primero hallar el bloque correspondiente usando la fórmula $\frac{x}{\texttt{block\\_size}}$ .

Luego, aplicar la diferencia correspondiente entre el elemento almacenado actualmente en $x$ y el elemento al que queremos cambiarlo.

Consultas de suma: $\mathcal{O}(\sqrt{N})$

Para realizar una consulta de suma de $[0\ldots r]$ , calcular

\sum_{i = 0}^{R-1} \texttt{blocks}[i] + \sum_{R \cdot \texttt{block\\_size}}^r \texttt{nums}[i]

donde $\texttt{blocks}[i]$ representa la suma total del $i$ -ésimo bloque, el $i$ -ésimo bloque representa la suma de los elementos del rango $[i\cdot \texttt{block\\_size},(i + 1)\cdot \texttt{block\\_size})$ , y $R=\left\lceil \frac{r}{\texttt{block\\_size}} \right\rceil$ .

Por último, $\sum_{i=l}^{r} \texttt{nums}[i]$ es la diferencia entre las dos sumas $\sum_{i=0}^{r}\texttt{nums}[i]$ y $\sum_{i=0}^{l-1}\texttt{nums}[i]$ , que se calculan cada una en $\mathcal{O}(\sqrt N)$ .

C++Java


#include <bits/stdc++.h>
using namespace std;
 
struct Sqrt {
	int block_size;
	vector<int> nums;
	vector<long long> blocks;
	Sqrt(int sqrtn, vector<int> &arr) : block_size(sqrtn), blocks(sqrtn, 0) {
		nums = arr;
		for (int i = 0; i < nums.size(); i++) { blocks[i / block_size] += nums[i]; }
	}
 
	/** O(1) update to set nums[x] to v */
	void update(int x, int v) {
		blocks[x / block_size] -= nums[x];
		nums[x] = v;
		blocks[x / block_size] += nums[x];
	}
 
	/** O(sqrt(n)) query for sum of [0, r) */
	long long query(int r) {
		long long res = 0;
		for (int i = 0; i < r / block_size; i++) { res += blocks[i]; }
		for (int i = (r / block_size) * block_size; i < r; i++) { res += nums[i]; }
		return res;
	}
 
	/** O(sqrt(n)) query for sum of [l, r) */
	long long query(int l, int r) { return query(r) - query(l - 1); }
};
 
int main() {
	int n, q;
	cin >> n >> q;
 
	vector<int> arr(n);
	for (int i = 0; i < n; i++) { cin >> arr[i]; }
	Sqrt sq((int)ceil(sqrt(n)), arr);
 
	for (int i = 0; i < q; i++) {
		int t, l, r;
		cin >> t >> l >> r;
		if (t == 1) {
			sq.update(l - 1, r);
		} else {
			cout << sq.query(l, r) << "\n";
		}
	}
}


import java.io.*;
import java.util.*;
 
public class DRSQ {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		int n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
 
		int[] arr = Arrays.stream(br.readLine().split(" "))
		                .mapToInt(Integer::parseInt)
		                .toArray();
		Sqrt sq = new Sqrt((int)Math.ceil(Math.sqrt(n)), arr);
 
		for (int i = 0; i < q; i++) {
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());
			int l = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
 
			if (type == 1) {
				sq.update(l - 1, r);
			} else {
				pw.println(sq.query(l, r));
			}
		}
 
		br.close();
		pw.close();
	}
 
	static class Sqrt {
		static int blockSize;
		static int[] nums;
		static long[] blocks;
 
		Sqrt(int sqrtn, int[] arr) {
			blockSize = sqrtn;
			blocks = new long[sqrtn];
			nums = arr;
			for (int i = 0; i < nums.length; i++) { blocks[i / blockSize] += nums[i]; }
		}
 
		/** O(1) update to set nums[x] to v */
		static void update(int x, int v) {
			blocks[x / blockSize] -= nums[x];
			nums[x] = v;
			blocks[x / blockSize] += nums[x];
		}
 
		/** O(sqrt(n)) query for sum of [l, r) */
		static long query(int l, int r) { return query(r) - query(l - 1); }
 
		/** O(sqrt(n)) query for sum of [0, r) */
		static long query(int r) {
			long res = 0;
			for (int i = 0; i < r / blockSize; i++) { res += blocks[i]; }
			for (int i = (r / blockSize) * blockSize; i < r; i++) { res += nums[i]; }
			return res;
		}
	}
}

Combinar algoritmos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	AC	Hop Sugoroku	Normal	Sqrt	en el módulo

Hacer este problema con DP tiene complejidad temporal $\mathcal{O}(N^2)$ .

C++


vector<int> dp(n, 1);
for (int i = n - 1; i >= 0; i--) {
	for (int x = i + a[i]; x <= n; x += a[i]) { dp[i] = (dp[i] + dp[x]) % MOD; }
}

Si intentamos sumas de prefijos, la complejidad sigue siendo $\mathcal{O}(N^2)$ .

C++


for (int i = n - 1; i >= 0; i--) {
	dp[i] += s[a[i]][i % a[i]];
	dp[i] %= MOD;
 
	for (int j = 1; j <= x; j++) {
		s[j][i % j] += dp[i];
		s[j][i % j] %= MOD;
	}
}

Podemos aplicar el algoritmo de DP a los pasos donde $A_i \cdot x >= \sqrt(N)$ porque el salto es más grande, lo que resulta en un bucle más rápido. Podemos aplicar sumas de prefijos para los casos restantes donde $A_i \cdot x < \sqrt(N)$ .

Este truco nos permite combinar dos algoritmos $\mathcal{O}(N^2)$ en un algoritmo $\mathcal{O}(N\sqrt(N))$ .

C++


#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 998244353;
 
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }
 
	int x = (int)sqrt(n);
 
	vector<int> dp(n, 1);
	vector<vector<int>> s(x + 1, vector<int>(x + 1));
	for (int i = n - 1; i >= 0; i--) {
		if (a[i] > x) {
			for (int j = i + a[i]; j < n; j += a[i]) {
				dp[i] += dp[j];
				dp[i] %= MOD;
			}
		} else {
			dp[i] += s[a[i]][i % a[i]];
			dp[i] %= MOD;
		}
		for (int j = 1; j <= x; j++) {
			s[j][i % j] += dp[i];
			s[j][i % j] %= MOD;
		}
	}
 
	cout << dp[0] << endl;
}

Procesamiento por lotes

Ver la sección de CPH sobre procesamiento por lotes (batch processing).

Mantener un “buffer” de las últimas actualizaciones (hasta $\sqrt N$ ). La respuesta de cada consulta de suma se puede calcular con sumas de prefijos y examinando cada actualización dentro del buffer. Cuando el buffer se vuelve demasiado grande ( $\ge \sqrt N$ ), vaciarlo y recalcular las sumas de prefijos.

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int n, q;
vector<int> arr;
vector<long long> prefix;
 
/** Build the prefix array for arr */
void build() {
	prefix[0] = 0;
	for (int i = 1; i <= n; i++) { prefix[i] = prefix[i - 1] + arr[i - 1]; }
}
 
int main() {
	cin >> n >> q;
	arr.resize(n);
	for (int i = 0; i < n; i++) { cin >> arr[i]; }
	prefix.assign(n + 1, 0);
	build();
 
	vector<pair<int, int>> updates;
	for (int i = 0; i < q; i++) {
		int type, a, b;
		cin >> type >> a >> b;
		if (type == 1) {
			a--;
			updates.push_back({a, b - arr[a]});
			arr[a] = b;
		} else {
			long long ans = prefix[b] - prefix[a - 1];
			a--, b--;
			for (const auto &[idx, val] : updates) {
				if (a <= idx && idx <= b) { ans += val; }
			}
			cout << ans << "\n";
		}
 
		// rebuild the prefix array once the buffer gets to sqrt(n)
		if (updates.size() * updates.size() >= n) {
			updates.clear();
			build();
		}
	}
}


import java.io.*;
import java.util.*;
 
public class DRSQ {
	static int[] arr;
	static List<Long> prefix;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		int n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
 
		arr = Arrays.stream(br.readLine().split(" "))
		          .mapToInt(Integer::parseInt)
		          .toArray();
		prefix = new ArrayList<>();
		prefix.add(0L);
		for (int i = 1; i <= arr.length; i++) {
			prefix.add(prefix.get(i - 1) + arr[i - 1]);
		}
 
		List<Pair> updates = new ArrayList<>();
		for (int i = 0; i < q; i++) {
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
 
			if (type == 1) {
				a--;
				updates.add(new Pair(a, b - arr[a]));
				arr[a] = b;
			} else {
				long ans = prefix.get(b) - prefix.get(a - 1);
				a--;
				b--;
				for (Pair p : updates) {
					if (a <= p.first && p.first <= b) { ans += p.second; }
				}
				pw.println(ans);
			}
 
			if (updates.size() * updates.size() >= n) {
				updates = new ArrayList<>();
				build();
			}
		}
 
		br.close();
		pw.close();
	}
 
	static void build() {
		for (int i = 1; i <= arr.length; i++) {
			prefix.set(i, prefix.get(i - 1) + arr[i - 1]);
		}
	}
 
	// BeginCodeSnip{Pair Class}
	private static class Pair {
		public int first;
		public int second;
		Pair(int a, int b) {
			first = a;
			second = b;
		}
	}
	// EndCodeSnip
}

Algoritmo de Mo

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	SPOJ	D-query	Difícil	Sqrt, Mo's Algorithm	en el módulo

Recursos
Fuente	Recurso	Notas
CF	Mo's Algorithm	muy breve descripción
HE	Mo's Algorithm	descripción elaborada con demostración
CPH	Mo's Algorithm - 27.3

C++Java


#include <bits/stdc++.h>
using namespace std;
 
struct Query {
	int l, r, idx;
};
 
int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) { cin >> v[i]; }
 
	int q;
	cin >> q;
	vector<Query> queries;
	for (int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;
		queries.push_back({--x, --y, i});
	}
 
	int block_size = (int)sqrt(n);
	auto mo_cmp = [&](Query a, Query b) {
		int block_a = a.l / block_size;
		int block_b = b.l / block_size;
		if (block_a == block_b) { return a.r < b.r; }
		return block_a < block_b;
	};
	sort(queries.begin(), queries.end(), mo_cmp);
 
	int different_values = 0;
	vector<int> values(VALMAX);
	auto remove = [&](int idx) {
		values[v[idx]]--;
		if (values[v[idx]] == 0) { different_values--; }
	};
	auto add = [&](int idx) {
		values[v[idx]]++;
		if (values[v[idx]] == 1) { different_values++; }
	};
 
	int mo_left = -1;
	int mo_right = -1;
	vector<int> ans(q);
	for (int i = 0; i < q; i++) {
		int left = queries[i].l;
		int right = queries[i].r;
 
		while (mo_left < left) { remove(mo_left++); }
		while (mo_left > left) { add(--mo_left); }
		while (mo_right < right) { add(++mo_right); }
		while (mo_right > right) { remove(mo_right--); }
 
		ans[queries[i].idx] = different_values;
	}
 
	for (int i = 0; i < q; i++) { cout << ans[i] << '\n'; }
}


import java.io.*;
import java.util.*;
 
public class Main {
	private static class Query {
		int l, r, idx;
		Query(int l, int r, int idx) {
			this.l = l;
			this.r = r;
			this.idx = idx;
		}
	}
 
	static int[] arr;
	static int[] values;
	static int differentValues = 0;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int n = Integer.parseInt(br.readLine());
		arr = new int[n];
		int MAX = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			MAX = Math.max(MAX, arr[i]);
		}
 
		values = new int[MAX + 1];
		List<Query> queries = new ArrayList<>();
		int q = Integer.parseInt(br.readLine());
		for (int i = 0; i < q; i++) {
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken()),
			    r = Integer.parseInt(st.nextToken());
			Query query = new Query(l - 1, r - 1, i);
			queries.add(query);
		}
		br.close();
 
		int blockSize = (int)Math.sqrt(n);
 
		Collections.sort(queries, (a, b) -> {
			int aBlock = a.l / blockSize;
			int bBlock = b.l / blockSize;
			if (aBlock != bBlock) { return aBlock - bBlock; }
			return a.r - b.r;
		});
 
		int moLeft = 0;
		int moRight = -1;
		int[] res = new int[q];
		for (int i = 0; i < q; i++) {
			int left = queries.get(i).l;
			int right = queries.get(i).r;
			while (moLeft < left) { remove(moLeft++); }
			while (moLeft > left) { add(--moLeft); }
			while (moRight < right) { add(++moRight); }
			while (moRight > right) { remove(moRight--); }
			res[queries.get(i).idx] = differentValues;
		}
 
		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < q; i++) { pw.println(res[i]); }
		pw.close();
	}
 
	private static void add(int idx) {
		int num = arr[idx];
		if (values[num] == 0) { differentValues++; }
		values[num]++;
	}
 
	private static void remove(int idx) {
		int num = arr[idx];
		if (values[num] == 1) { differentValues--; }
		values[num]--;
	}
}

Notas adicionales

Cotas bajas (p. ej. $n=5\cdot 10^4$ ) y/o límites de tiempo altos (más de 2s) pueden ser señales de que se espera descomposición por raíz cuadrada.
CPH 262:
En la práctica, no es necesario usar el valor exacto de $\sqrt n$ como parámetro, y en su lugar podemos usar parámetros $k$ y $n/k$ donde $k$ es distinto de $\sqrt n$ . El parámetro óptimo depende del problema y de la entrada. Por ejemplo, si un algoritmo recorre a menudo los bloques pero rara vez inspecciona elementos individuales dentro de los bloques, puede ser buena idea dividir el arreglo en $k<\sqrt n$ bloques, cada uno de los cuales contiene $n/k > \sqrt n$ elementos.
Si una actualización toma tiempo proporcional al tamaño de un bloque ( $\mathcal{O}(n/k)$ ) mientras que una consulta toma tiempo proporcional al número de bloques por $\log n$ ( $\mathcal{O}(k\log n)$ ) entonces podemos tomar $k\approx \sqrt{\frac{n}{\log n}}$ para que tanto actualizaciones como consultas tomen tiempo $\mathcal{O}(\sqrt{n\log n})$ .
Las soluciones con peores complejidades no son necesariamente más lentas (al menos para problemas con tamaños de entrada razonables, p. ej. $n\le 5\cdot 10^5$ ). Recuerdo un caso en que una solución rápida $\mathcal{O}(n\sqrt n\log n)$ pasó (donde el $\log n$ venía de un BIT) mientras que una solución $\mathcal{O}(n\sqrt n)$ no. ¡Los factores constantes importan!

Sobre árboles

Recursos
Fuente	Recurso	Notas
CF	Mo's on Trees
CF	Block Tree
CF	SQRT decomposition for beginners	el formato no es el mejor pero el ejemplo de árbol está bien

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	SPOJ	COT2 - Count on a tree II	Normal	Sqrt, Mo's Algorithm, Trees	en el módulo

Explicación

Usaremos la técnica del tour de Euler para aplanar el árbol en un arreglo, sobre el cual podemos aplicar el algoritmo de Mo. Si el nodo $x$ es ancestro del nodo $y$ , entonces el camino de $x$ a $y$ en nuestro arreglo es $[\texttt{start}[x], \texttt{start}[y]]$ . En caso contrario, el camino del nodo $x$ al nodo $y$ es equivalente al subarreglo $[\texttt{end}[x],\texttt{start}[y]]$ , más el LCA mismo, que no está incluido en el rango. Esto funciona porque el tour de Euler incluye cada nodo dos veces: una cuando el DFS entra y otra cuando el DFS sale. Como solo los nodos de nuestro camino no se habrán salido, esto garantiza que no sobrecontamos ningún nodo de subárbol.

Implementación

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

C++


#include <algorithm>
#include <cmath>
#include <iostream>
#include <unordered_map>
#include <vector>
 
using namespace std;
 
const int MAXN = 1e5;
const int MAXQ = 1e6;
const int MAXLOG = 18;
 
int n, q, timer, block_size, distinct;
int v[MAXN + 5], ans[MAXQ + 5];
int depth[MAXN + 5], node_at[MAXN + 5];
int start[MAXN + 5], en[MAXN + 5];
int up[MAXN + 5][MAXLOG + 5];
bool seen[MAXN];
vector<vector<int>> g(MAXN + 5);
unordered_map<int, int> mp;
 
struct Query {
	int l, r, lca, id;
	bool operator<(const Query &oth) const {
		int b1 = l / block_size, b2 = oth.l / block_size;
		return b1 < b2 || (b1 == b2 && r < oth.r);
	}
};
 
vector<Query> queries;
 
void dfs(int node, int parent) {
	start[node] = ++timer;
	node_at[timer] = node;
	depth[node] = depth[parent] + 1;
	up[node][0] = parent;
	for (int i = 1; i < MAXLOG; i++) { up[node][i] = up[up[node][i - 1]][i - 1]; }
	for (int son : g[node]) {
		if (son == parent) { continue; }
		dfs(son, node);
	}
	en[node] = ++timer;
	node_at[timer] = node;
}
 
int get_lca(int x, int y) {
	if (depth[x] > depth[y]) { swap(x, y); }
	int diff = depth[y] - depth[x];
	for (int i = 0; (1 << i) <= diff; i++) {
		if ((1 << i) & diff) { y = up[y][i]; }
	}
	if (x == y) { return x; }
	for (int i = MAXLOG; i >= 0; i--) {
		if (up[x][i] != up[y][i]) {
			x = up[x][i];
			y = up[y][i];
		}
	}
	return up[x][0];
}
 
void add_value(int node) {
	if (seen[node]) {
		if (--mp[v[node]] == 0) { distinct--; }
	} else {
		if (mp[v[node]]++ == 0) { distinct++; }
	}
	seen[node] = !seen[node];
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	cin >> n >> q;
 
	for (int i = 1; i <= n; i++) { cin >> v[i]; }
 
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
 
	dfs(1, 1);
 
	block_size = (int)sqrt(2 * n);
 
	for (int i = 1; i <= q; i++) {
		int x, y;
		cin >> x >> y;
		if (start[x] > start[y]) { swap(x, y); }
		int l = get_lca(x, y);
		if (l == x) {
			queries.push_back({start[x], start[y], -1, i});
		} else {
			queries.push_back({en[x], start[y], l, i});
		}
	}
 
	sort(queries.begin(), queries.end());
 
	for (int i = 0, l = 1, r = 0; i < q; i++) {
		while (l > queries[i].l) { add_value(node_at[--l]); }
		while (r < queries[i].r) { add_value(node_at[++r]); }
		while (l < queries[i].l) { add_value(node_at[l++]); }
		while (r > queries[i].r) { add_value(node_at[r--]); }
 
		// Check the lca value
		int lc = queries[i].lca;
		if (lc != -1) { add_value(lc); }
		ans[queries[i].id] = distinct;
		if (lc != -1) { add_value(lc); }
	}
 
	for (int i = 1; i <= q; i++) { cout << ans[i] << '\n'; }
 
	return 0;
}

Problemas

Conjunto A

Problemas donde la mejor solución involucra descomposición por raíz cuadrada.

Fuente	Nombre	Dificultad	Tags	Solución
CF	Points on Plane	Fácil	Sqrt	Solución
POI	2017 - Containers	Fácil	Sqrt	Solución
CF	Holes	Fácil	Sqrt	—
CF	Ann and Books	Fácil	Sqrt	—
JOI	★ 2018 - Bitaro's Birthday	Normal	Sqrt, DP	Solución
YS	Static Range Inversions Query	Normal	Sqrt	Solución
CF	Powerful array	Normal	Mo's Algorithm	—
APIO	2019 - Bridges	Difícil	Sqrt	Solución
CF	Tree and Queries	Difícil	Sqrt, Tree, Euler Tour	—
JOI	2018 - Snake Escaping	Difícil	SOS DP	Solución
Platinum	Train Tracking	Muy difícil	Sqrt	—
DMOPC	Fluid Dynamics	Muy difícil	Sqrt	Solución
Wesley's Anger Contest	Arithmetic Subtrees	Muy difícil	Sqrt	—

Conjunto B

Problemas que se pueden resolver sin ella. ¡Pero igual se puede intentar usarla!

Fuente	Nombre	Dificultad	Tags	Solución
JOI	2019 - Examination	Normal	Mo's Algorithm, 2DRQ	—
IOI	2009 - Regions	Normal	Sqrt	Solución
Platinum	Minimizing Haybales	Normal	Sqrt	Solución
Platinum	New Barns	Difícil	Sqrt	Solución
CF	Tree Queries	Difícil	Sqrt	—
CF	The Tree	Difícil	HLD	Solución
TLX	Tree Game	Difícil	Sqrt	—
CSA	Shopping Time	Difícil	Sqrt	—
Old Gold	Fencing the Herd	Difícil	Convex	—
CF	The Awesomest Vertex	Muy difícil	Convex	—
IOI	2011 - Dancing Elephants	Muy difícil	Sqrt	—
Platinum	Cow At Large	Muy difícil	Sqrt	Solución
IOI	2015 - Teams	Muy difícil	2DRQ	—