Somma Prefissa (Prefix Sum)
Le somme prefisse sono estremamente utili quando si lavora con intervalli in un array. Spesso è possibile ottimizzare notevolmente i programmi utilizzando la somma prefissa di un array invece di calcolare la somma a ogni richiesta.
Immagina di dover rispondere a molte richieste (anche milioni) del tipo: “Qual è la somma degli elementi dell’array
a dall’inizio fino a ?”. Un approccio ingenuo sarebbe calcolare ogni volta la somma a[0] + a[1] + a[2] + ... + a[]. Ad esempio, se abbiamo un array e delle query:a = [8, 3, -2, 4, 10, -1, 0, 5] # array
q = [3, 5, 2, 7] # query (richieste)Potremmo eseguire un ciclo
for per calcolare la somma a[0] + a[1] + a[2] + ... + a[] per ogni query, ma così faremmo molti calcoli ripetuti: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]Noterai che la prima parte del calcolo è sempre la stessa. Prima di calcolare
res2, conosciamo già il risultato di a[0] + a[1] + a[2] + a[3], che corrispondeva a res1. Prima di calcolare res4, sappiamo già quanto vale la somma a[0] + a[1] + a[2] + a[3] + a[4] + a[5]. È evidente che possiamo ottimizzare questi calcoli e rispondere alle richieste istantaneamente invece di lanciare un ciclo for per ogni domanda.Per farlo, possiamo memorizzare un nuovo array
p di somme prefisse, in cui gli elementi di p rappresentano la somma degli elementi dell’array a fino a quell’indice. In questo modo, la risposta a ogni richiesta sarà semplicemente accedere a un elemento dell’array delle somme prefisse: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]Osserva lo schema: per calcolare l’elemento successivo nell’array
p, riprendiamo tutto ciò che avevamo già sommato in quello precedente e aggiungiamo un altro elemento di a. In questo modo, sfruttiamo i calcoli precedenti evitando di sommare gli stessi numeri più volte: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]Questo può essere calcolato con un singolo ciclo
for in tempo lineare, anziché eseguire più cicli che ripetono gli stessi calcoli. Dopo aver creato l’array delle somme prefisse p, potremo rispondere a tutte le nostre richieste all’istante, perché p[i] contiene la somma a[0] + a[1] + a[2] + ... + a[i]. Quindi, per ogni query , la risposta sarà semplicemente p[].Puoi calcolare ora l’array delle somme prefisse?
Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ ). La seconda riga contiene n interi separati da spazio, che rappresentano l’array a .Output
Il programma deve stampare l’array delle somme prefisse di
a.Esempi
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