Soma prefixada
As somas prefixadas (prefix sums) são extremamente úteis ao trabalhar com intervalos em arrays. Muitas vezes, é possível otimizar programas por meio do uso da soma prefixada de um array, em vez de calcular a soma repetidamente a cada consulta.
Imagine um problema em que precisamos responder a inúmeras consultas (podendo chegar a milhões), todas do tipo: “Qual será a soma dos elementos do array a do início até ?”. Uma abordagem ingênua consistiria em calcular a soma
a[0] + a[1] + a[2] + ... + a[] a cada vez. Como exemplo, se tivermos um array e consultas:a = [8, 3, -2, 4, 10, -1, 0, 5] # array
q = [3, 5, 2, 7] # queriesPoderíamos usar um loop para calcular a soma
a[0] + a[1] + a[2] + ... + a[] para cada consulta, resultando em muitos cálculos repetidos: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]Perceba que a parte inicial do cálculo se repete. Antes de calcular
res2, já conhecemos o resultado de a[0] + a[1] + a[2] + a[3], que era exatamente res1. Antes de calcular res4, já sabemos o valor de a[0] + a[1] + a[2] + a[3] + a[4] + a[5]. É perfeitamente possível otimizar essas contas e responder às consultas instantaneamente, sem necessidade de somar todos os elementos toda vez.Para isso, podemos armazenar um novo array
p para as somas prefixadas, em que cada elemento de p representa a soma dos elementos do array a até aquele índice. Assim, a resposta para cada consulta será simplesmente acessar um elemento de p: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]Note o padrão: para calcular o próximo elemento em
p, aproveitamos os resultados do elemento anterior e adicionamos apenas o próximo valor de a. Isso evita somar os mesmos números repetidas vezes: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]Esse array p pode ser construído com um único loop em tempo linear, em vez de múltiplos loops que repetem sempre o mesmo cálculo. Após criar o array de somas prefixadas
p, podemos responder a todas as consultas imediatamente, pois p[i] guarda a soma a[0] + a[1] + a[2] + ... + a[i]. Assim, para cada consulta , a resposta será simplesmente p[].Consegue calcular o array de soma prefixada agora?
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ). A segunda linha contém n inteiros separados por espaço representando o array a .Saída
O programa deve exibir o array de somas prefixadas de
a.Exemplos
Entrada | Saída |
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