Adaptive Dynamic Bitvectors
<|reference_start|>Adaptive Dynamic Bitvectors: While operations \emph{rank} and \emph{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 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.<|reference_end|>
@article{navarro2024adaptive,
    title={Adaptive Dynamic Bitvectors},
    author={Gonzalo Navarro},
    journal={arXiv preprint arXiv:2405.15088},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.15088},
    primaryClass={cs.DS}
}