While operations rank and select on static bitvectors can be supported in constant time, lower bounds show that supporting updates raises the cost per operation to \(\Theta (\log n/ \log \log n)\) on bitvectors holding n bits. This is a shame in scenarios where updates are possible but uncommon. We develop a representation of bitvectors that we call adaptive dynamic bitvector, which uses the asymptotically optimal \(n+o(n)\) bits of space and, if there are q queries per update, supports all the operations in \(O(\log (n/q)/\log \log n)\) amortized time. Further, we prove that this time is worst-case optimal in the cell probe model. We describe a large number of applications of our representation to other compact dynamic data structures.
