Rekursiver Segmentbaum
Sie haben ein Array mit
n Elementen. Ihre Aufgabe ist es, einen Segmentbaum rekursiv zu erstellen und den Wert jedes Knotens in diesem Baum zu berechnen. Dabei gibt der Wert jedes Knotens die Summe des jeweiligen Teilarrays an, das er repräsentiert.Eingabe
Die erste Zeile der Eingabe enthält eine ganze Zahl
n (1 ≤ n ≤ 100 000), welche die Anzahl der Elemente im Array angibt.Die zweite Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9), die die Elemente des Arrays darstellen.Ausgabe
Geben Sie den Segmentbaum mit den Werten aller Knoten aus. Jede Ebene des Segmentbaums soll in einer eigenen Zeile ausgegeben werden, wobei die Werte jeweils durch ein Leerzeichen getrennt sind.
Beispiele
Eingabe | Ausgabe |
4
1 2 3 4 | 10
3 7
1 2 3 4 |
8
3 7 9 6 2 1 5 4 | 37
25 12
10 15 3 9
3 7 9 6 2 1 5 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 10 MB