Adaptive Dynamic Bitvectors
Gonzalo Navarro
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). This is a
shame in
scenarios where updates are possible but uncommon. We develop a representation
of bitvectors that, if there are q queries per update, supports
all the operations in O(log(n/q)) amortized time. Our experimental results support the theoretical findings, displaying speedups of orders of
magnitude compared to standard dynamic implementations.