Calcular la suma de los k elementos más pequeños en un BST (árbol de búsqueda binaria)
Dado un árbol de búsqueda binaria (BST) inicial vacío, se te pide realizar 2 tipos de consultas:
insert x- inserta el valorxen el BST
sum k- imprime la suma de los k elementos más pequeños en el BST
Se te dan
q consultas y tu objetivo es escribir un programa que ejecute todas estas consultas.Input
La primera línea de la entrada contiene un único número
q (1 ≤ q ≤ 1000).Las siguientes
q líneas contienen las consultas. Para todas las consultas insert, el valor de x no excede en valor absoluto. Para todas las consultas sum, el valor de k no excede el tamaño actual del árbol.Output
Para cada consulta
sum, el programa debe imprimir la suma de los k elementos más pequeños en el árbol de búsqueda binaria.Examples
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