Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa | |||
algoritmos-oia:estructuras:tablita-aditiva [2017/12/26 19:15] sebach ↷ Page moved from algoritmos-oia:tablita-aditiva to algoritmos-oia:estructuras:tablita-aditiva |
algoritmos-oia:estructuras:tablita-aditiva [2018/01/06 00:13] 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)$. |