Suma de prefijos (Prefix sum)
Las sumas de prefijos resultan muy útiles al trabajar con rangos dentro de un arreglo. En muchos casos, es posible optimizar los programas reemplazando el cálculo repetitivo de sumas por el uso de una suma de prefijos.
Imagina un problema en el que se deben responder muchas consultas (millones) del tipo: “¿Cuál es la suma de los elementos del arreglo
a desde el inicio hasta ?”. Una solución ingenua sería calcular la suma a[0] + a[1] + a[2] + ... + a[] en cada consulta. Por ejemplo, si tenemos un arreglo y las siguientes consultas:a = [8, 3, -2, 4, 10, -1, 0, 5] # array
q = [3, 5, 2, 7] # queriesPodríamos usar un ciclo
for y calcular cada suma:res1 = a[0] + a[1] + a[2] + a[3]
res2 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
res3 = a[0] + a[1] + a[2]
res4 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]Observa que la primera parte del cálculo se repite siempre. Antes de calcular
res2, ya conocemos el resultado de a[0] + a[1] + a[2] + a[3] (que es res1). Antes de calcular res4, también sabemos la suma de a[0] + a[1] + a[2] + a[3] + a[4] + a[5]. Podemos aprovechar estas repeticiones y responder cada consulta de manera instantánea en lugar de ejecutar un ciclo for en cada ocasión.Para ello, crearemos un nuevo arreglo
p de sumas de prefijos, donde los elementos de p representen la suma de los elementos en el arreglo original a hasta cada índice. De esta forma, la respuesta a cada consulta será simplemente acceder a un elemento de la suma de prefijos:p[0] = a[0]
p[1] = a[0] + a[1]
p[2] = a[0] + a[1] + a[2]
p[3] = a[0] + a[1] + a[2] + a[3]
p[4] = a[0] + a[1] + a[2] + a[3] + a[4]
p[5] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
p[6] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6]
p[7] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]Observa el patrón: para calcular el siguiente elemento en el arreglo de sumas de prefijos
p, repetimos todo lo que ya teníamos y agregamos un elemento más de a. Así, podemos aprovechar los cálculos previos y evitar sumar los mismos números una y otra vez:p[0] = a[0]
p[1] = p[0] + a[1]
p[2] = p[1] + a[2]
p[3] = p[2] + a[3]
p[4] = p[3] + a[4]
p[5] = p[4] + a[5]
p[6] = p[5] + a[6]
p[7] = p[6] + a[7]Esto puede hacerse con un único ciclo
for en tiempo lineal, en vez de múltiples ciclos que repitan la misma operación una y otra vez. Después de calcular el arreglo de sumas de prefijos p, podremos responder todas las consultas al instante, pues p[i] contiene la suma a[0] + a[1] + a[2] + ... + a[i]. Por lo tanto, para cada consulta , la respuesta será simplemente p[].¿Podrías calcular ahora el arreglo de sumas de prefijos?
Entrada
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ ). La segunda línea de la entrada contiene n enteros separados por espacios que representan el arreglo a .Salida
El programa debe imprimir el arreglo de sumas de prefijos de
a.Ejemplos
Input | Output |
8
8 3 -2 4 10 -1 0 5 | 8 11 9 13 23 22 22 27 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 20 MB