k-ая порядковая статистика на отрезке

[jobs]

Добрый день всем!
Пытаюсь разобраться в решении задачи о k-порядковой статистике на отрезке
Я знаю только решение с персистентным деревом отрезков, однако оно довольно сложно в реализации, да и асимптотика O(log N) на запрос не нужна. Слышал, что есть решение с обычным деревом отрезков, в котором в каждой вершине хранится отсортированный подмассив. Как получать ответ на запрос в таком дереве? Ведь могут существовать отрезки, которых нет в дереве