Key points are not available for this paper at this time.
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 (n/ n). This is a shame in scenarios where updates are possible but uncommon. We develop a representation of bitvectors that, if there are q = (² n) queries per update, supports all the operations in O ( (n/q) ) amortized time. Our experimental results support the theoretical findings, displaying speedups of orders of magnitude compared to standard dynamic implementations.
Gonzalo Navarro (2024) studied this question.