Find the smallest value that appears in .
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: .