algorithm - 有效地找到位集中第 k 个设置位的位置

Question

我有一个稀疏位集，可能有数百万甚至数十亿位宽。假设 bitset 已经被有效地压缩，并且假设我也已经可以有效地查询 bitset 以查看在某个给定范围(即位置和长度)中设置了多少位。

鉴于此，我能否有效地找到位集中第 k 个设置位的位置，或者有效地指示它不存在？对编程语言中立的算法的描述将是理想的。假设我无法更改 bitset 实现的任何内部结构……也就是说，我可以对 bitset 做的唯一事情就是查询它的总宽度，并询问它在任何给定范围内设置了多少位。

Answer 1

如果您可以高效地查询每个范围内设置的位数，则可以对 #set_bits(0,i) 执行二分查找以找到该值等于 k 的第一个索引。

需要O(log(n)*f(n))，其中f(n)是#set_bits(0, i) 操作。