如何从Fenwick树中有效地找到连续的已用/空闲插槽范围

Question

假设我正在跟踪Fenwick树中插槽的使用情况.例如,让我们考虑跟踪32个插槽,导致Fenwick树布局,如下图所示,其中网格中的数字表示底层数组中的索引,其中计数由Fenwick树操纵,其中每个单元格中的值为该段中"已使用"项的总和(即阵列单元23存储范围[16-23]中使用的时隙量).最低级别的项目(即单元格0,2,4,...)只能具有值"1"(使用的槽)或"0"(空闲槽).

我正在寻找的是一种有效的算法来查找给定数量的连续空闲时隙的第一个范围.

为了说明,假设我有如下图所示的Fenwick树,其中总共使用了9个插槽(请注意,为了清晰起见,仅添加浅灰色数字,而不是实际存储在树的数组单元中).

现在我想找到例如10个空闲插槽的第一个连续范围,它应该找到这个范围:

我似乎无法找到一种有效的方法,这让我有点头疼.请注意,由于所需的存储空间量对我的目的而言至关重要,因此我不希望将设计扩展为细分树.

对O(log N)类型的解决方案的任何想法和建议都将非常受欢迎.

编辑

赏金期限到期后的更新时间.感谢所有意见,问题,建议和答案.他们让我重新思考问题,教会了我很多并向我指出(再一次,有一天我可以学到这一课),我应该更多地关注我在提问时要解决的问题.

由于@Erik P是唯一一个对包含所请求的代码/伪代码的问题提供合理答案的人,因此他将获得赏金.

他还正确地指出使用这种结构的O(log N)搜索是不可能的.荣誉对@DanBjorge提供一个证明,让我想想最坏情况下的性能.

@EvgenyKluev的评论和回答让我意识到我应该以不同的方式提出我的问题.事实上,我已经在很大程度上做了他的建议(参见https://gist.github.com/anonymous/7594508 - 显示我在发布此问题之前遇到的问题),并问这个问题,希望能有效率搜索连续范围的方法,从而防止将此设计更改为段树(这将需要额外的1024字节).然而,似乎这种改变可能是明智之举.

对于任何感兴趣的人,可以在这里找到与此问题中使用的示例匹配的二进制编码Fenwick树(以64位编码的32插槽fenwick树):https://gist.github.com/anonymous/7594245 .

Answer 1

我认为以 O(log N) 时间复杂度实现所有所需功能并同时最小化内存需求的最简单方法是使用位向量来存储所有 0/1（空闲/已用）值。位向量可以替代 Fenwick 树和线段树的 6 个最低层（如果实现为 64 位整数）。因此，这些树的高度可能会减少 6 倍，每棵树的空间需求将比平常减少 64（或 32）倍。

线段树可以实现为位于数组中的隐式二叉树（就像众所周知的最大堆实现一样）。根节点位于索引 1 处，索引处节点的每个左后代i位于2*i，每个右后代位于2*i+1。这意味着与 Fenwick 树相比需要两倍的空间，但由于树高减少了 6 层，所以这不是一个大问题。

每个线段树节点应存储一个值 - 从该节点覆盖的点开始的“空闲”槽的最长连续序列的长度（如果不存在这样的起点，则为零）。这使得搜索给定数量的连续零的第一个范围非常简单：从根开始，如果它包含大于或等于所需的值，则选择左后代，否则选择右后代。到达某个叶节点后，检查位向量的相应字（字中间是否有一系列零）。

更新操作比较复杂。当将值更改为“used”时，检查位向量的适当字，如果为空，则上升线段树以找到某些左后代的非零值，然后下降树以该值到达最右边的叶子，然后确定新的添加的槽将“空闲”间隔分成两半，然后更新添加的槽的所有父节点和被分割的间隔的起始节点，还在位向量中设置一个位。将值改变为“免费”可以类似地实现。

如果还需要获取某个范围内的非零项的数量，请在相同的位向量上实现 Fenwick 树（但与线段树分开）。芬威克树的实现没有什么特别之处，只是将 6 个最低节点加在一起由位向量的某些字的“总体计数”操作代替。有关使用 Fenwick 树和位向量的示例，请参阅CodeChef 上Magic Board的第一个解决方案。

使用各种按位技巧可以非常有效地实现位向量的所有必要操作。对于其中一些（前导/尾随零计数和总体计数），您可以使用编译器内部函数或汇编器指令（取决于目标体系结构）。

如果使用 64 位字和树节点（使用 32 位字）实现位向量，则除了位向量之外，两棵树都占用 150% 的空间。如果每个叶节点不对应于单个位向量字，而是对应于小范围（4 或 8 个字），则这可能会显着减少。对于 8 个字，树所需的额外空间仅为位向量大小的 20%。这使得实现稍微复杂一些。如果优化得当，性能应该与每个叶节点一个字的变体大致相同。对于非常大的数据集，性能可能会更好（因为位向量计算比遍历树更适合缓存）。