Herramientas de usuario
algoritmos-oia:estructuras:tablita-aditiva
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:estructuras:tablita-aditiva [2017/12/11 14:20] ariel |
algoritmos-oia:estructuras:tablita-aditiva [2018/01/06 00:13] (actual) ariel |
||
|---|---|---|---|
| Línea 24: | Línea 24: | ||
| 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]. | 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]. | ||
| - | FIXME: Insertar dibujito lindo. | + | $$\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)$. | 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]. | 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)$. | Usando esta fórmula y que S[0] = 0, podemos calcular el vector S en $O(n)$. | ||
| Línea 55: | Línea 57: | ||
| ===== El caso de dos dimensiones ===== | ===== El caso de dos dimensiones ===== | ||
| - | **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$. | + | **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)$. | 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$). | ||
| + | |||
| + | FIXME: Agregar dibujos explicativos. | ||
| + | |||
| + | Usando estas dos observaciones podemos calcular S en $O(nm)$ y responder todas las consultas en $O(q)$. | ||
| + | |||
| + | === Implementación === | ||
| + | |||
| + | <code cpp> | ||
| + | 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]; | ||
| + | } | ||
| + | } | ||
| + | </code> | ||
| + | |||
| FIXME: Explicar el problema en más dimensiones. | FIXME: Explicar el problema en más dimensiones. | ||
algoritmos-oia/estructuras/tablita-aditiva.1513002050.txt.gz · Última modificación: 2017/12/11 14:20 por ariel
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
