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)$. |