Today we continue our exploration of succinct data structures by exploring the binary selection problem, essentially the inverse of rank queries. Our goal is to preprocess an bitvector $A$ to answer queries of the form "what is the index of the $k$th 1 bit in the array?" In doing so, we'll see that many of the techniques we used to solve binary rank are not one-offs and instead standard techniques for reducing space usage in environments where every bit counts.
Links