Tema 4
Suma de prefijos y arreglo de diferencias
Patrón de examen
Suma de prefijos para múltiples consultas de suma en rangos. Diferencias para múltiples actualizaciones de rangos. Combínalos para problemas complejos.
Explicación
Suma de prefijos
Permite calcular la suma de cualquier rango [l, r] en O(1) luego de una precalculación O(n).
pre[0] = 0
pre[i] = pre[i-1] + a[i]
suma(l, r) = pre[r] - pre[l-1]
Suma de prefijos 2D
Para consultas de suma en subrectángulos de una matriz.
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]
suma(r1,c1,r2,c2) = pre[r2][c2] - pre[r1-1][c2]
- pre[r2][c1-1] + pre[r1-1][c1-1]
Arreglo de diferencias
Permite actualizar un rango [l, r] sumando un valor x en O(1), luego reconstruir el arreglo en O(n).
diff[l] += x
diff[r+1] -= x
// Para reconstruir: a[i] = a[i-1] + diff[i]
Caso de uso: "Suma x a todos los elementos del rango [l,r]" para Q consultas.