K-th smallest in wavelet matrix:
function kthSmallest(l, r, k)
result := 0
for level from log(sigma) - 1 down to 0
zeros_l := rank0(bitvectors[level], l)
zeros_r := rank0(bitvectors[level], r + 1)
count := zeros_r - zeros_l
if k <= count then
// Answer has bit 0 at this level
l := zeros_l
r := zeros_r - 1
else
// Answer has bit 1 at this level
result := result or (1 << level)
ones_before := zeros[level]
l := ones_before + (l - zeros_l)
r := ones_before + (r + 1 - zeros_r) - 1
k := k - count
return result
Same complexity, but faster constants due to no pointer chasing.