Optimal Indexes for Sparse Bit Vectors

Alexander Golynski, Alessio Orlandi, Rajeev Raman +1

We consider the problem of supporting Rank() and Select() operations on a bit vector of length m with n 1 bits. The problem is considered in the succinct index model, where the bit…