Structure
Root: bit per element saying 'small half or large half'. Left child: elements from small half. Right child: from large half. Recurse.
Advertisement
Rank query
How many i's equal to c in prefix [0, r]? Descend tree tracking new position via bit rank. O(log Σ) steps.
Advertisement
kth in range
Descend based on which side contains k-th. Bit position gives child position. O(log Σ) total.
Space
O(N log Σ) bits. Way less than merge sort tree.