La división por raíz cuadrada, aunque su nombre sugiere una relación con la recursión, se trata más de una técnica de optimización o una estrategia de resolución. Su esencia radica en dividir las consultas en dos categorías basadas en un umbral, S. Cada categoría se aborda con un método distinto: una puede resolverse de forma exhaustiva (fuerza bruta) y la otra mediante preprocesamiento y mantenimiento dinámico.

El algoritmo de raíz cuadrada se puede describir como una forma elegante de aplicar fuerza bruta.

Los problemas que implican saltos de un número específico de pasos a menudo se benefician de la división por raíz cuadrada.

Ejemplo 1: P3396 - Conflicto de Hash

Este problema es equivalente a calcular la suma de elementos en índices y, y + x, y + 2x, etc. Una solución de fuerza bruta que recorre cada consulta desde y podría tener una complejidad de hasta O(nm). Al observar que para valores grandes de m, la cantidad de números a sumar es pequeña, podemos establecer un punto de corte en √n. Si el paso (o módulo) m es mayor que √n, podemos obtener el resultado en aproximadamente O(√n). Si el paso m es menor que √n, necesitamos preprocesar la información para realizar consultas en O(1).

Consideremos el preprocesamiento: s[i][j] representa la suma de todos los números con un paso de i y un punto de inicio de j. Calcular la contribución de cada punto de inicio para cada paso requiere una complejidad de tiempo de O(n√n).

Ahora, consideremos las actualizaciones. Cada vez que un valor cambia, necesitamos mantener actualizado el arreglo s. Esto implica calcular el impacto de la actualización actual en cada paso.

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>

const int MAXN = 510;
long long s[MAXN][MAXN];

void solve() {
   int n, q;
   std::cin >> n >> q;
   std::vector<int> a(n + 1);
   for (int i = 1; i <= n; ++i) {
       std::cin >> a[i];
   }

   int m = sqrt(n);
   // Preprocesar casos con módulo pequeño
   for (int i = 1; i <= n; ++i) {
       for (int j = 1; j <= m; ++j) {
           s[j][i % j] += a[i];
       }
   }

   while (q--) {
       char op;
       std::cin >> op;
       int x, y;
       std::cin >> x >> y;
       if (op == 'A') {
           // Consultar resultados preprocesados para módulo pequeño
           if (x <= m) {
               std::cout << s[x][y] << std::endl;
           } else {
               // Calcular fuerza bruta para pasos grandes
               long long ans = 0;
               for (int i = y; i <= n; i += x) {
                   ans += a[i];
               }
               std::cout << ans << std::endl;
           }
       } else {
           // Actualizar el arreglo s al cambiar un elemento
           for (int i = 1; i <= m; ++i) {
               s[i][x % i] += y - a[x];
           }
           a[x] = y;
       }
   }
}

int main() {
   std::ios::sync_with_stdio(false);
   std::cin.tie(0);
   std::cout.tie(0);
   solve();
   return 0;
}
	

Ejemplo 2: F. Problema del Resto

La lógica es similar al problema anterior. Es crucial elegir el valor de m apropiado, como √500000, para evitar tiempo de espera excedido (TLE) debido al número de consultas t.

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>

const int MAXN = 500010;
const int MAXM = 800; // Aproximadamente sqrt(500000)
long long s[MAXM][MAXM];
int a[MAXN];

void solve() {
   int n_limit = 500000; // Límite superior para el tamaño del arreglo (implícito)
   int m = sqrt(400000); // Umbral para la división por raíz cuadrada

   int q;
   std::cin >> q;
   while (q--) {
       int op, x, y;
       std::cin >> op >> x >> y;
       if (op == 1) {
           // Actualización
           for (int i = 1; i <= m; ++i) {
               s[i][x % i] += y;
           }
           a[x] += y;
       } else {
           // Consulta
           if (x <= m) {
               // Si el paso es pequeño, usar resultados precalculados
               std::cout << s[x][y] << "\n";
           } else {
               // Si el paso es grande, calcular fuerza bruta
               long long ans = 0;
               for (int i = y; i <= n_limit; i += x) {
                   ans += a[i];
               }
               std::cout << ans << "\n";
           }
       }
   }
}

int main() {
   std::ios::sync_with_stdio(false);
   std::cin.tie(0);
   std::cout.tie(0);
   solve();
   return 0;
}
	

Ejemplo 3: E. Consultas de Arreglo

Esta es una excelente pregunta que combina programación dinámica (DP) con división por raíz cuadrada. La idea clave es no descartar una solución simplemente porque parece demasiado lenta o incorrecta a primera vista.

Definamos f[i][j] como la cantidad de veces que se debe sumar i y j para que el valor supere n.

Considerando la transición:
Si i + j + a[i] > n, entonces f[i][j] = 1.
Si i + j + a[i] <= n, entonces f[i][j] = f[i + a[i] + j][j] + 1.

Si j y a[i] se manejan con fuerza bruta, la complejidad sería O(n^2). Al aplicar la división por raíz cuadrada, si k (el número de saltos) es grande, los saltos son rápidos y superan n rápidamente. En este caso, la fuerza bruta es eficiente. Si k es pequeño, utilizamos la DP para la transición de estado y el procesamiento de consultas.

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>

const int MAXN = 100010;
const int MAX_SQRT = 330; // Aproximadamente sqrt(100010)
int s[MAXN][MAX_SQRT];

void solve() {
   int n;
   std::cin >> n;
   std::vector<int> a(n + 1);
   for (int i = 1; i <= n; ++i) {
       std::cin >> a[i];
   }

   int m = sqrt(n); // Umbral para la división por raíz cuadrada

   // Preprocesamiento para valores de 'j' (paso) pequeños
   for (int i = n; i >= 1; --i) {
       for (int j = 1; j <= m; ++j) {
           if (i + a[i] + j > n) {
               s[i][j] = 1;
           } else {
               s[i][j] = s[i + a[i] + j][j] + 1;
           }
       }
   }

   int q;
   std::cin >> q;
   while (q--) {
       int x, y;
       std::cin >> x >> y;
       // Si el paso 'y' es pequeño, consultar resultados precalculados
       if (y <= m) {
           std::cout << s[x][y] << "\n";
       } else {
           // Si el paso 'y' es grande, calcular fuerza bruta
           int ans = 0;
           while (x <= n) {
               ++ans;
               x += a[x] + y;
           }
           std::cout << ans << "\n";
       }
   }
}

int main() {
   std::ios::sync_with_stdio(false);
   std::cin.tie(0);
   std::cout.tie(0);
   solve();
   return 0;
}
	

Ejemplo 4: F. Suma de Progresiones

Los problemas que implican saltos múltiples a menudo sugieren el uso de la división por raíz cuadrada. Si no hubiera coeficientes o pesos adicionales, sería un problema clásico de suma de progresiones. Con coeficientes y pesos, debemos considerar cómo manejarlos. Aquí, mantenemos dos arreglos: f y g. El arreglo f almacena la suma prefijada de pesos, pero con saltos de d. El arreglo g almacena la suma prefijada simple.

La fórmula para f[i][j] implica términos como (s/d)*a[s] + (s/d + 1)*a[s+d] + ....

La fórmula para g[i][j] implica términos como a[s] + a[s+d] + a[s+2d] + ....

La respuesta que buscamos es...

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>

const int MAX_SQRT = 330; // Aproximadamente sqrt(N)
const int MAXN = 100010;
long long f[MAX_SQRT][MAXN]; // Suma prefijada ponderada
long long g[MAX_SQRT][MAXN]; // Suma prefijada simple

void solve() {
   int n, q;
   std::cin >> n >> q;
   std::vector<int> a(n + 1);
   for (int i = 1; i <= n; ++i) {
       std::cin >> a[i];
   }

   int sq = sqrt(n); // Umbral para la división por raíz cuadrada

   // Preprocesamiento para pasos (d) pequeños
   for (int d = 1; d <= sq; ++d) {
       for (int j = 1; j <= n; ++j) {
           // Calculando la suma ponderada y simple para cada paso 'd'
           // Nota: La lógica exacta de los pesos puede variar según la interpretación del problema.
           // Este código asume una forma de ponderación simple para fines ilustrativos.
           // La fórmula original en el texto requiere una interpretación más detallada para ser implementada correctamente.

           // Ejemplo de cálculo para g (suma simple con saltos de d)
           g[d][j] = (j - d >= 0 ? g[d][j - d] : 0) + a[j];

           // Ejemplo de cálculo para f (suma ponderada con saltos de d)
           // La ponderación 'j / d' es una posible interpretación.
           f[d][j] = (j - d >= 0 ? f[d][j - d] : 0) + (j / d) * a[j];
       }
   }

   while (q--) {
       int s, d, k;
       std::cin >> s >> d >> k;
       // Si el paso 'd' es pequeño, usar resultados precalculados
       if (d <= sq) {
           long long current_f = f[d][s + (k - 1) * d] - (s - d >= 0 ? f[d][s - d] : 0);
           long long current_g = g[d][s + (k - 1) * d] - (s - d >= 0 ? g[d][s - d] : 0);

           // Ajuste de la fórmula basada en la interpretación de los pesos y la progresión.
           // La fórmula original requiere aclaración para una implementación precisa.
           // Este es un ejemplo de cómo se podría usar f y g:
           long long ans = current_f - (s / d - 1) * current_g; // Esta fórmula es especulativa
           std::cout << ans << ' ';
       } else {
           // Si el paso 'd' es grande, calcular fuerza bruta
           long long ans = 0;
           for (int i = s, j = 1; j <= k; i += d, ++j) {
               ans += j * a[i]; // Asumiendo que 'j' es el peso
           }
           std::cout << ans << ' ';
       }
   }
   std::cout << std::endl;
}

int main() {
   std::ios::sync_with_stdio(false);
   std::cin.tie(0);
   std::cout.tie(0);
   int t;
   std::cin >> t;
   while (t--) {
       solve();
   }
   return 0;
}