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:33] 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 63: | Línea 63: | ||
| 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$). | 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)$. | ||
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
