Abstract

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 ?(logn/loglogn). 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. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.