Find the -th smallest value in .
This is where wavelet trees shine. Persistent segment trees also achieve per query, but wavelet trees use less space and support more query types.
function kthSmallest(node, l, r, k)
if node.lo = node.hi then
return node.lo
// Count elements going left
leftCount := rank0(node.bitvector, r + 1) - rank0(node.bitvector, l)
if k <= leftCount then
// Answer is in left subtree
newL := rank0(node.bitvector, l)
newR := rank0(node.bitvector, r + 1) - 1
return kthSmallest(node.left, newL, newR, k)
else
// Answer is in right subtree
newL := rank1(node.bitvector, l)
newR := rank1(node.bitvector, r + 1) - 1
return kthSmallest(node.right, newL, newR, k - leftCount)
Time: .