Fenwick-Tree에서 k 번째로 작은 원소를 찾는 O (klogn) 시간 알고리즘

Question

나는 O(k log(n)) 시간에 펜윅 트리에서 kth 가장 작은 실제 주파수를 찾으려고합니다.
내 데이터 인 경우 :

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

그래서 두 번째 작은 요소는

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; 
} 

시작은 해답이 될한다, 그럼 내가 가능한 해결책을 생각 1.

Answer 1

인덱스 것 .

Answer 2

실제 주파수를 정렬하지 않고는 k 번째로 작은 실제 주파수가 필요하다고 생각합니다. 가지고있는 것만이 펜윅 나무라면, O (log (n))의 모든 실제 주파수를 계산할 수 있으므로 O (n * log (n)) 시간에 실제 주파수의 시퀀스를 계산할 수 있습니다. (here 참조), n 개의 주파수가 있습니다. quicksort로 실제 주파수 시퀀스를 정렬하면 O (n * log (n))이되며 정렬 된 시퀀스의 k 번째 요소는 O (n)이됩니다 (동일한 실제 빈도를 가진 항목이있을 수 있으므로 O (1)에서는 이것을 할 수 없지만 선형 검색을 사용할 수 있습니다). 따라서 전체 검색은 O (n * log (n))에서 수행 할 수 있습니다.

희망이 도움이됩니다. 나는 이것이 O (k * log (n))에서 어떻게 될 수 있는지 전혀 모른다.