Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:estructuras:tablita-aditiva [2017/12/11 14:20]
ariel
+++ algoritmos-oia:estructuras:tablita-aditiva [2017/12/26 19:15]
sebach ↷ Page moved from algoritmos-oia:tablita-aditiva to algoritmos-oia:estructuras:tablita-aditiva
@@ Línea 55: / Línea 55: @@
 ===== 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)$.
+**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.

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página