Zakładam, ze k może się zmieniać. Wtedy można to zrobić drzewem przedziałowym (w tym przypadku drzewem licznikowym). Dla każdego wierzchołka musisz wiedzieć ile wartości jest w jego poddrzewie. Wyszukiwanie działa podobnie jak quick search. Jak szukasz k-tego elementu to z danego wierzchołka możesz albo pójśc do lewego poddrzewa (gdy k <= liczba wierzchołków w lewym poddrzewie) albo prawego (wtedy k -= liczba wierzchołków w lewym poddrzewie).
Odpowiadanie na jedno zapytanie ma złożonosć O(logn), tak samo usuwanie/dodawanie wartości do drzewa.
Inne rozwiązania tego problemu: https://forum.pasja-informatyki.pl/581253/implementacja-seta-z-idxami-drzewa-licznikowego