Encontre a soma dos k menores elementos em uma BST (árvore binária de pesquisa)
Dada uma árvore binária de pesquisa vazia, sem quaisquer nós, você precisa executar 2 tipos de consultas:
insert x– insere o valorxna BST
sum k– exibe a soma doskmenores elementos na BST
Sendo
q o número de consultas, você deve escrever um programa para executar essas consultas.Entrada
A primeira linha da entrada contém um único número
q (1 ≤ q ≤ 1000).As próximas
q linhas contêm as consultas. Para todas as consultas insert, o valor de x não excede em valor absoluto. Para todas as consultas sum, o valor de k não excede o tamanho atual da árvore.Saída
Para cada consulta
sum, o programa deve imprimir a soma dos k menores elementos na árvore binária de pesquisa.Exemplos
Entrada | Saída |
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