O (klogn) to find the k-th smallest element from the Fenwick tree

Question

I want to find the smallest actual frequency kth in the Fenwick tree in O(k log(n)) .
If my details are:

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

So, the second smallest element will have index 1.

Answer 1

Well, I was thinking about a possible solution,

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

the beginning should be the answer.

Answer 2

You need the smallest actual frequency, which, I think, cannot be determined without sorting the actual frequencies. If the only thing you have is the Fenwick tree, then you can calculate the sequence of actual frequencies in O (n * log (n)) time (since you can calculate each individual actual frequency in O (log (n)) (see here ) and you have n frequencies). Sorting a sequence of actual frequencies with quicksort takes O (n * log (n)) , and finding the k-th element of the sorted sequence takes O (n) (maybe records with the same actual frequency, so you cannot do this in O (1 ), but you can use linear search). Thus, the entire search can be performed in O (n * log (n)).

Hope this helps. I do not know how this can be done in O (k * log (n)).