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 Última revisión Ambos lados, revisión siguiente | ||
|
algoritmos-oia:estructuras:tablita-aditiva [2017/12/11 14:29] ariel [El caso de dos dimensiones] |
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 62: | Línea 62: | ||
| 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]. | 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>0$ y $j>0$). | + | 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)$. | 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.txt · Última modificación: 2018/01/06 00:13 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
