Tablita aditiva

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:

Si $a = 2$ y $b = 3$ , sólo tenemos que sumar la posición $2$ y la respuesta sería $4$ .
Si $a = 0$ y $b = 6$ , tenemos que devolver la suma de todas las posiciones del vector, la respuesta es $1+2+4+0-3+2 = 6$ .
Si $a = 1$ y $b = 4$ , tenemos que sumar las posiciones $1$ , $2$ y $3$ , por lo que la respuesta es $2+4+0 = 6$ .

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:

S[0] = 0
S[1] = 1
S[2] = 1 + 2
S[3] = 1 + 2 + 4
S[4] = 1 + 2 + 4 + 0
S[5] = 1 + 2 + 4 + 0 - 3
S[6] = 1 + 2 + 4 + 0 - 3 + 2

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].

$\overbrace{\underbrace{A[0] + A[1] + \ldots + A[a-1]}_{s[a]} + \underbrace{A[a] + A[a+1] + \ldots + A[b-1]}_{s[b]-s[a]}}^{s[b]}$

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].

$\overbrace{\underbrace{A[0] + A[1] + \ldots + A[i-2]}_{s[i-1]} + A[i-1]}^{s[i]}$

Usando esta fórmula y que S[0] = 0, podemos calcular el vector S en $O(n)$ .

Implementació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];
        }
}

El caso de dos dimensiones

Problema: Supongamos ahora que en lugar de un vector, tenemos una matriz bidimensional M 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)$ .

Solución: Nuevamente vamos a crear una estructura que guarde la suma de algunos rectángulos especiales. Esta vez, guardamos una matriz S de tamaño $(n+1) \times (m+1)$ donde cada posición $(i,j)$ guarda la suma del rectángulo $[0,i) \times [0, j)$ , es decir, el rectángulo de vértice superior izquierdo $(0,0)$ y vértice inferior derecho $(i,j)$ .

Ahora, dada una consulta $a, b, c, d$ , podemos responder la consulta en $O(1)$ usando S como S[c][d] - S[a][d] - S[c][b] + S[a][b].

Para calcular S eficientemente, hay varias maneras, una de ellas es notar que S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i-1][j-1] (si $i,j>0$ ).

: Agregar dibujos explicativos.

Usando estas dos observaciones podemos calcular S en $O(nm)$ y responder todas las consultas en $O(q)$ .

Implementación

void sumasSubrectangulos(vector<vector<long long>> M){
	int n = M.size(); //cantidad de filas
        int m = M[0].size(); //cantidad de columnas (ojo si n = 0)
        vector<vector<long long>> S(n+1, vector<long long>(m+1, 0)); //S de tamaño n+1 x m+1 inicializado en 0
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i-1][j-1];
            }
        }
 
        int q; //cantidad de consultas
        cin >> q;
        for(int i = 0; i < q; i++) {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            cout << S[c][d] - S[a][d] - S[c][b] + S[a][b];
        }
}

: Explicar el problema en más dimensiones.

Problemas

guardias

latas

frutales

sigmatriz