Hard · Fenwick Order Statistic
Understand → Visualise → Practice.
Frequencies describe a sorted multiset of integer indices. Return the index containing each one-based kth element.
Store frequencies in a Fenwick tree. To find the kth element, descend by powers of two, skipping any block whose count is smaller than the k you still need.
Build a Fenwick tree where index i holds how many copies of value i the multiset has.
Start with the largest power of two ≤ n. If the block at pos + step holds fewer than k items, move past it and subtract its count from k.
After all steps, the answer is the index just after your position. Each query costs O(log n).
O(n) to build and O(log n) per query, with O(n) space.
Queries are one-based (k = 1 is the smallest element), while the returned indices are zero-based.
Read the full guide first: Fenwick Trees and Segment Trees.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.