Segmentbaum
TODO: Ausführlichere Segmentbaum-Erklärung
Ein Segmentbaum (Segment Tree) ist eine auf binären Bäumen basierende Datenstruktur, die ein gegebenes Array oder eine Liste von Elementen repräsentiert. Jeder Knoten im Baum steht für ein Segment oder einen Teilbereich des ursprünglichen Arrays.
In einem Segmentbaum repräsentiert der Wurzelknoten das gesamte Array, während die Blattknoten die einzelnen Elemente dieses Arrays darstellen. Die internen Knoten stehen für Segmente, die durch das Aufteilen des Arrays in kleinere Teilbereiche entstehen.
Üblicherweise gilt: Repräsentiert ein Knoten das Teilsegment [l, r], so steht sein linkes Kind für das Teilsegment [l, (l+r)/2], während das rechte Kind das Teilsegment [(l+r)/2 + 1, r] übernimmt. Diese rekursive Aufteilung setzt sich fort, bis jedes Blatt genau ein einzelnes Element des ursprünglichen Arrays repräsentiert.
Der in jedem Knoten des Segmentbaums gespeicherte Wert hängt von der jeweiligen Problemstellung oder der auszuführenden Abfrage ab. Häufig werden Segmentbäume genutzt, um Summen, Minimal- oder Maximalwerte oder andere Operationen in einem gegebenen Teilbereich schnell zu berechnen. Der an einem Knoten gespeicherte Wert wird dabei aus den Werten seiner Kindknoten abgeleitet.
Segmentbäume sind besonders nützlich, wenn es darum geht, Bereichsabfragen oder Aktualisierungen auf einem Array durchzuführen. Durch den Aufbau eines Segmentbaums können diese Operationen mit einer Zeitkomplexität von O(log N) effizient ausgeführt werden, wobei N die Größe des ursprünglichen Arrays ist.
Zusammenfassend bietet der Segmentbaum eine leistungsfähige Datenstruktur, um bereichsbasierte Operationen auf Arrays durchzuführen und sowohl Abfragen als auch Aktualisierungen effizient umzusetzen. Er findet in zahlreichen Algorithmen und Problemstellungen Anwendung, etwa bei abfragebasierten Intervallen, Bereichsupdates und vielem mehr.
Aufgabe: Iterative Berechnung der Segmentbaum-Knoten
Es ist ein Array mit n Elementen gegeben. Deine Aufgabe besteht darin, einen Segmentbaum iterativ zu konstruieren und den Wert jedes Knotens im Baum zu berechnen. Der Wert eines Knotens ist die Summe des entsprechenden Teilsegments, das er repräsentiert.
Eingabe
Die erste Zeile enthält eine ganze Zahl n (1 ≤ n ≤ 100 000), die die Anzahl der Elemente im Array angibt.
Die zweite Zeile enthält n durch Leerzeichen getrennte ganze Zahlen () – dies sind die Elemente des Arrays.
Ausgabe
Gib den Segmentbaum mit allen Werten der Knoten aus. Jede Ebene des Segmentbaums soll in einer eigenen Zeile ausgegeben werden, wobei die Werte durch 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