Finde die Summe der k kleinsten Elemente in einem BST
Ausgehend von einem leeren Binary Search Tree (BST) ohne Knoten sollen zwei Arten von Abfragen durchgeführt werden:
insert x – fügt den Wert x in den BST ein
sum k – gibt die Summe der k kleinsten Elemente im BST aus
Bei insgesamt q Abfragen soll ein Programm geschrieben werden, das diese Abfragen ausführt.
Eingabe
Die erste Zeile der Eingabe enthält die Zahl q (1 ≤ q ≤ 1000).
Die nächsten q Zeilen enthalten die Abfragen. Für alle insert-Abfragen gilt, dass der Wert x nicht größer als ±10^9 ist. Für alle sum-Abfragen gilt, dass k nicht größer als die aktuelle Größe des Baums ist.
Ausgabe
Für jede sum-Abfrage soll das Programm die Summe der kleinsten k Elemente im Binary Search Tree ausgeben.
Beispiele
Eingabe
Ausgabe
8 insert 2 insert 1 sum 1 sum 2 insert 10 insert 20 sum 3 sum 2