Please suggest a fast method to find pth element in frequency table?

consider a sorted array with xi , xi+1, xi+2, … , xi+n distinct elements with frequencies a0,a1,a2,…,an respectively. How can i find pth element in this?

If you want to find pth element for many queries then just take cummulative frequency:
i.e,
Make an array c, such that c[i] = a[i] + a[i-1] .. ... a[0].
Now you can just perform a binary search on c to find what pth element is.
For suppose c = \{{1,5,7,8\}} and you want to find 4th element just perform binary search to find the lowest index for which c[i] \geq p which is 2 1 in this case (c[1] = 5 > 4).

1 Like

This can be done using “segment tree” if you have online queries (i.e. with update)…

Refer this answer of mine after the “view content” box…
https://discuss.codechef.com/questions/129286/how-to-solve-krillin/129291

For offline queries(without upadte) you can easily do with a binary search on “prefix sum array” of frequencies…

#maybe “fenwick tree” is also applicable here…

1 Like