Trouver la somme des k plus petits éléments dans un BST
Étant donné un arbre binaire de recherche (ABR, Binary Search Tree) vide, c’est-à-dire sans aucun nœud, il vous est demandé d’exécuter 2 types de requêtes :
insert x– insérer la valeurxdans le BST
sum k– afficher la somme deskplus petits éléments dans le BST
Avec
q requêtes, vous devez écrire un programme qui exécute chacune de ces requêtes.Entrée
La première ligne d’entrée contient un seul nombre
q (1 ≤ q ≤ 1000).Les
q lignes suivantes contiennent des requêtes. Pour toutes les requêtes insert, la valeur de x ne dépasse pas en valeur absolue. Pour toutes les requêtes sum, la valeur de k ne dépasse pas la taille actuelle de l’arbre.Sortie
Pour chaque requête
sum, le programme doit afficher la somme des k plus petits éléments dans l’arbre binaire de recherche.Exemples
Entrée | Sortie |
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