DE
RU
EN
ES
ZH
FR
PT
AR
HI
Rekursiver Aufbau eines balancierten Baums aus Präfixsummen
C++
Hard
recursion
Aufgabe «Rekursiver Aufbau eines balancierten Baums aus Präfixsummen»
Gegeben ist ein Array A aus ganzen Zahlen der Größe N. Es soll rekursiv ein binärer Baum aufgebaut werden, bei dem jeder Knoten die Präfixsumme der Elemente im Intervall [l, r) sowie die Indizes l und r enthält. Die Wurzel entspricht dem Intervall [0, N). Teilen Sie das Intervall rekursiv in zwei Hälften (linke Hälfte [l, mid), rechte Hälfte [mid, r)), bis die Länge des Intervalls 1 beträgt. Berechnen Sie für jeden Knoten die Summe der Elemente in seinem Intervall. Geben Sie den Baum in der Tiefensuche-Reihenfolge (pre-order) aus: Geben Sie für jeden Knoten l, r und die Summe aus. Verwenden Sie Rekursion. N <= 100, die Zahlen im Array haben einen Betrag <= 10^6.
Eingabeformat
Erste Zeile: Ganzzahl N (1 <= N <= 100). Zweite Zeile: N ganze Zahlen A[i] (-10^6 <= A[i] <= 10^6).
Ausgabeformat
Geben Sie für jeden Knoten in pre-order-Reihenfolge drei Zahlen aus: l, r, sum. Jeder Knoten in einer eigenen Zeile. Wenn das Intervall leer ist (l == r), geben Sie nichts aus.
Beispiele
Beispiel 1
EINGABE
4
1 2 3 4
AUSGABE
0 4 10
0 2 3
0 1 1
1 2 2
2 4 7
2 3 3
3 4 4
Beispiel 2
EINGABE
2
-5 5
AUSGABE
0 2 0
0 1 -5
1 2 5
main.cpp