Successor in Range

Find the smallest value $\geq v$ that appears in $A[l..r]$.

function successor(node, l, r, v)
    if l > r then
        return infinity
    if node.lo = node.hi then
        return node.lo if node.lo >= v else infinity

    mid := (node.lo + node.hi) / 2

    leftL := rank0(node.bitvector, l)
    leftR := rank0(node.bitvector, r + 1) - 1
    rightL := rank1(node.bitvector, l)
    rightR := rank1(node.bitvector, r + 1) - 1

    if v <= mid then
        result := successor(node.left, leftL, leftR, v)
        if result <= mid then
            return result
    return successor(node.right, rightL, rightR, v)

Try left subtree first (smaller values). If no valid element found, try right.

Time: $O(\log \sigma)$.