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 Wertxin 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 | 1
3
13
3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB