Trova la somma dei k elementi minori in un BST
Dato un Binary Search Tree (BST, albero di ricerca binario) inizialmente vuoto e senza nodi, ti viene chiesto di eseguire 2 tipi di query:
insert x– inserisce il valorexnel BST
sum k– stampa la somma deikelementi più piccoli presenti nel BST
Avendo
q query, l’obiettivo è scrivere un programma che esegua queste operazioni.Input
La prima riga dell’input contiene un singolo numero
q (1 ≤ q ≤ 1000).Le successive
q righe contengono le query. Per tutte le query di tipo insert, il valore di x non supera in valore assoluto. Per tutte le query di tipo sum, il valore di k non è più grande della dimensione corrente dell’albero.Output
Per ogni query di tipo
sum, il programma deve stampare la somma dei k elementi più piccoli presenti nel BST.Esempi
Input | Output |
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