K-th Smallest in Range

Find the $k$-th smallest value in $A[l..r]$.

This is where wavelet trees shine. Persistent segment trees also achieve $O(\log n)$ 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: $O(\log \sigma)$.