¡Esta es una revisión vieja del documento!
Supongamos que queremos resolver el siguiente problema:
Problema: Tenemos un vector A de $n$ números enteros. Nos llegan $q$ consultas que preguntan por la suma de los elementos de un intervalo del vector. Es decir, cada consulta consiste de dos enteros $a, b$ con $0 \leq a < b \leq n$ y debemos responder la suma de los elementos de todas las posiciones $i$ con $a \leq i < b$. Queremos responder todas las consultas en $O(n+q)$.
Por ejemplo, si A = [1, 2, 4, 0, -3, 2], estas serían posibles consultas y sus respectivas respuestas:
Solución: La idea será crear una estructura auxiliar que me permita responder rápidamente una consulta sin la necesidad de recorrer todo el intervalo. La estructura que usaremos será un vector $S$ de $n+1$ posiciones donde guardaremos las suma de algunos intervalos estratégicamente elegidos. En concreto, en la posición $i$ del vector S guardamos la suma de los números de A para todas las posiciones menores a $i$.
Por ejemplo, si nuevamente, el vector original es [1, 2, 4, 0, -3, 2] entonces S será [0, 1, 3, 7, 7, 4, 6] pues:
Supongamos que tenemos nuestro vector S calculado ¿Cómo nos ayuda S a responder las consultas rápido? Si nos llega la consula $a$, $b$, queremos sumar los números en posiciones menores a $b$ y mayores o iguales a $a$. En S[b] tenemos la suma de los números en posiciones menores a $b$, pero estamos sumando números de más. Nos sobran los números en posiciones menores a $a$ ¡Pero esto es justamente S[a]! Luego, podemos dar la respuesta como S[b] - S[a].
: Insertar dibujito lindo.
Con esto podemos responder cada consulta en $O(1)$, tardando en total $O(q)$ en responder todas. Todavía nos queda el problema de calcular S eficientemente, ya que el algoritmo que consiste en calcular cada elemento de S sumando todos los números del intervalo correspondiente es $O(n^2)$.
La observación clave es que si queremos calcular el elemento $i$ de S podemos aprovechar que ya calculamos el $i-1$ (si $i>0$), S[i-1] tiene la suma de los números en posiciones menores a la $i-1$, el único que me falta sumar para conseguir S[i] (las posiciones menores a $i$) es el número de la posición $i-1$. Luego, S[i] = S[i-1] + A[i-1].
Usando esta fórmula y que S[0] = 0, podemos calcular el vector S en $O(n)$.
void sumasSubintervalos(vector<long long> A){ int n = A.size(); //tamaño del vector vector<long long> S(n+1, 0); //S de tamaño n+1 inicializado en 0 for(int i = 1; i <= n; i++) { S[i] = S[i-1] + A[i-1]; } int q; //cantidad de consultas cin >> q; for(int i = 0; i < q; i++) { int a, b; cin >> a >> b; cout << S[b] - S[a]; } }
Problema: Supongamos ahora que en lugar de un vector, tenemos una matriz bidimensional de tamaño $n \times m$ y ahora las consulas en lugar de pedir la suma de un intervalos, piden la suma de un rectángulo de números de la matriz. Es decir, las $q$ consultas nos dan cuatro enteros $a, b, c, d$ con $0 \leq a < c \leq n$ y $0 \leq b < d \leq m$ y debemos responder la suma de los números en el rectángulo de $[a,c) \times [b,d)$ ó, lo que es lo mismo, la suma de las posiciones $(i, j)$ de la matriz con $a \leq i < c$ y $b \leq j < d$. Queremos ahora responder todas las consultas en $O(nm+q)$.
: Explicar el problema en más dimensiones.