Preguntar cuánto suma un tramo de un arreglo cuesta recorrerlo. Si la pregunta se va a repetir miles de veces, conviene pagar una pasada al principio y que cada consulta salga en tiempo constante. Es la primera forma de cambiar preprocesamiento por velocidad.
«¿Cuánto se vendió entre el día 100 y el día 250?» Con el arreglo de ventas a mano, la respuesta
es recorrer 150 posiciones y sumar. Rápido, si la pregunta se hace una vez.
El problema aparece cuando la pregunta se hace cien mil veces con rangos distintos: son cien mil
recorridos sobre los mismos números. Una pasada de preprocesamiento convierte cada una de esas
consultas en una resta.
Guardar los totales hasta cada posición
La idea es un arreglo auxiliar donde cada posición guarda la suma de todo lo que hay antes:
P[i]=j<i∑A[j],P[0]=0.
Con eso, la suma del tramo [desde,hasta) es una resta:
j=desde∑hasta−1A[j]=P[hasta]−P[desde].
La construcción y una consulta
El arreglo original, A.
1 / 8
A = [3, 1, 4, 1, 5]. La consulta de las posiciones 1 a 3 inclusive es P[4] − P[1] = 9 − 3 = 6, que es 1 + 4 + 1.
const prefixSums = (values: readonly number[]): number[] => { const sums = new Array<number>(values.length + 1).fill(0); for (let index = 0; index < values.length; index += 1) { sums[index + 1] = sums[index] + values[index]; } return sums;};/** Suma de values[from..to], con los dos extremos incluidos. */const rangeSum = (sums: readonly number[], from: number, to: number): number => sums[to + 1] - sums[from];
Cuándo conviene pagar el preprocesamiento
Sin preprocesar
Con sumas acumuladas
Construcción
Nada
O(n), una sola pasada
Memoria extra
Nada
O(n)
Cada consulta
O(largo del rango)
O(1): dos lecturas y una resta
Modificar un elemento
O(1)
O(n): hay que rehacer todo lo que sigue
La última fila es la que decide: las sumas acumuladas son para datos que no cambian, o que cambian mucho menos de lo que se consultan.
Antes de seguir, predecí
El truco inverso: el arreglo de diferencias
Hay un caso simétrico y muy útil: muchas modificaciones por rango y una sola lectura al final.
«Sumale 5 a todos los días entre el 100 y el 250», repetido cien mil veces.
La técnica es la inversa: en vez de acumular, se guardan diferencias. Para sumar v al rango
[desde,hasta] alcanzan dos escrituras:
D[desde]+=v,D[hasta+1]−=v.
Al final, la suma acumulada de D reconstruye el arreglo con todas las modificaciones aplicadas.
Seis días en cero. D tiene una posición extra para el cierre.
1 / 6
Dos modificaciones por rango cuestan dos escrituras cada una. La acumulada final, una sola pasada, deja el arreglo con todo aplicado.
En dos dimensiones
La misma idea sirve para submatrices, con un detalle: la esquina que se resta dos veces hay que
devolverla.
Cada celda de P guarda la suma del rectángulo desde el origen hasta ella. Consultar cualquier submatriz son cuatro lecturas: se restan dos rectángulos y se devuelve la intersección, que quedó restada dos veces.