Order Statistics with BIT

BIT can answer: "what is the $k$-th smallest element currently in the structure?"

Approach: binary search on the prefix sum.

function kthSmallest(k):
    pos = 0
    for i = LOG down to 0:  // LOG = log2(n)
        if pos + (1 << i) <= n and tree[pos + (1 << i)] < k:
            pos += (1 << i)
            k -= tree[pos]
    return pos + 1

This descends the BIT structure bit by bit, similar to binary lifting.

Use case: maintain a dynamic multiset, supporting insert, delete, and k-th element queries in $O(\log n)$ each.