Алгоритм времени O(klogn), чтобы найти k-й наименьший элемент из дерева Фенвика

Question

Я имею в виду, чтобы найти kth наименьшая фактическая частота в Fenwick-Tree в O(k log(n)) время.
Если мои данные:

Tree = [1,3,1,10,3]
Actual frequency = [1,2,1,6,3]

Таким образом, второй наименьший элемент будет по индексу 1.

Answer 1

Ну, я подумал о возможном решении,

while(start<=end){
   int mid=(start+end)>>1;
   if(read(mid)>=k)end=mid-1; // read(mid) returns the cummulative frequency.
   else start=mid+1;
}

начало должно быть ответом.

Answer 2

Вам нужна kth наименьшая фактическая частота, которую, я думаю, невозможно определить без сортировки фактических частот. Если единственное, что у вас есть, это дерево Фенвика, то вы можете вычислить последовательность фактических частот за O(n*log(n)) (поскольку вы можете рассчитать каждую фактическую частоту в O(log (n))) (см. здесь), и у вас есть n частот). Для сортировки последовательности фактических частот по быстрой сортировке требуется O(n*log(n)), а для поиска k-го элемента отсортированной последовательности - O(n) (могут быть записи с той же фактической частотой, поэтому вы не можете сделать это в O(1), но вы можете использовать линейный поиск). Таким образом, весь поиск может быть выполнен в O(n*log(n)).

Надеюсь это поможет. Я понятия не имею, как это можно сделать в O(k * log (n)).