Wavelet Matrix Operations

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 $O(\log \sigma)$ complexity, but faster constants due to no pointer chasing.