Präfixsummen
Präfixsummen sind äußerst praktisch, wenn man in Arrays mit verschiedenen Teilbereichen arbeiten muss. Häufig kann man Programme erheblich beschleunigen, indem man statt jeder einzelnen Summenberechnung die bereits vorberechnete Präfixsumme eines Arrays verwendet.
Stellen Sie sich ein Problem vor, bei dem wir sehr viele Anfragen (vielleicht sogar Millionen) der Form beantworten müssen: „Welchen Wert hat die Summe der Elemente des Arrays
a vom Anfang bis zu ?“ Eine naive Herangehensweise wäre, diese Summe a[0] + a[1] + a[2] + ... + a[] bei jeder Anfrage komplett neu zu berechnen.a = [8, 3, -2, 4, 10, -1, 0, 5] # array
q = [3, 5, 2, 7] # querieskönnten wir zwar für jede Anfrage eine Schleife verwenden, die
a[0] + a[1] + a[2] + ... + a[] berechnet, aber dabei entstehen viele unnötige Wiederholungen: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]Man sieht hier deutlich, dass wir Teile der Summe wiederholt berechnen. Vor der Berechnung von
res2 kennen wir bereits das Ergebnis von a[0] + a[1] + a[2] + a[3], was genau res1 war. Auch vor der Berechnung von res4 haben wir schon das Ergebnis für a[0] + a[1] + a[2] + a[3] + a[4] + a[5]. All diese sich wiederholenden Rechenschritte lassen sich vermeiden, sodass wir die Anfragen sogar unmittelbar beantworten können, ohne für jede wieder alle Elemente aufzuaddieren.Dazu legen wir ein neues Array
p an, in dem die Präfixsummen von a gespeichert werden. Das bedeutet, jedes Element von p enthält die Summe aller Elemente von a bis zu dem jeweiligen Index. Anschließend genügt es, für eine Anfrage einfach nur ein Element aus diesem Präfix-Array abzufragen: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]Man erkennt, dass hier bei jedem nächsten Element der bereits bekannte Wert der vorherigen Präfixsumme nur noch um ein weiteres Element aus
a ergänzt wird. So vermeiden wir es, immer wieder dieselben Zahlen zu addieren: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]Diese Präfixsummen können in einer einzigen Schleife in linearer Zeit berechnet werden. Anschließend lassen sich alle Anfragen sofort beantworten, denn
p[i] enthält direkt den Wert für a[0] + a[1] + a[2] + ... + a[i]. Das bedeutet: Für jede Anfrage genügt der Zugriff auf p[].Können Sie nun das Präfixsummen-Array berechnen?
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ). Die zweite Zeile enthält n durch Leerzeichen getrennte ganze Zahlen, die das Array a beschreiben .Ausgabe
Das Programm soll das Präfixsummen-Array von
a ausgeben.Beispiele
Eingabe | Ausgabe |
8
8 3 -2 4 10 -1 0 5 | 8 11 9 13 23 22 22 27 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 20 MB