对数方法动态化 | Codeboy's Blog

形式陈述

对数方法把可分解的静态查询结构改成支持插入的分层结构。设当前对象为有限集合，查询 $q$ 在不交并上可由各块答案组合：

Answer(q,A\sqcup B)=Combine(Answer(q,A),Answer(q,B)).

例如成员查询取逻辑或，计数查询求和。本节先承诺每次插入的键尚未出现；若字典接口还要求检测同键并覆盖旧值，定位与更新旧记录的费用必须另外计入。

维护块 $B_0,B_1,\ldots$ ，其中 $B_i$ 为空或恰含 $2^i$ 个键，同一层最多一块，各块互不相交且并为当前集合。空集合没有非空块，其查询返回相应空答案。

插入先形成一个单键块。若该层已有块，合并两块并在更高层构建新结构，像二进制进位一样继续。令 $R(s)$ 为这次合并并重建大小 $s$ 结构的成本；它包含收集记录和必要预处理。若只有黑盒静态构建算法 $P(s)$ ，可用 $R(s)=O(P(s)+s)$ ；若两块已有可利用的次序，可能更便宜。

直觉

层占用位就是键数的二进制表示。一个键每次参与更高层重建，所在块大小至少翻倍，因此不会在同一层被反复重建。查询则要访问所有当前非空块，再按原问题的组合规则合成答案。

这种结构保存的是一组不同大小的静态索引。它与分治法共享分组合并的图像，但这里的层次由更新进位形成，不要求每个静态建表过程本身也是分治算法。

例子与边界

当前有大小1、2、4的三个有序块，插入一个新键时，临时单键块依次归并成大小2、4、8的块。每次线性归并利用了两输入已经有序的条件，因此 $R(s)=O(s)$ ；它不同于从任意无序键重新排序的 $P(s)=O(s\log s)$ 。

成员查询在每个非空数组二分，再对命中结果取或，总成本为 $O(\log^2(n+1))$ 。已保证新键不重复时，插入的重建部分为摊还 $O(\log(n+1))$ ；若每次都先用这套查询检查重复，完整插入接口还要加上查询费用。

一般查询成本为

\sum_{i:B_i\ne\varnothing}Q(2^i)+C_{combine},

其中组合成本按真实答案表示计算。若 $Q$ 非减且每块答案可常数时间合并，才可简写为 $O(Q(n)\log(n+1))$ 。报告型答案还要支付输出和必要的合并、去重成本。

可分解性也需要证明。知道各块的最近点，可以比较距离取全局最近点；仅知道每块的某个全局路径摘要，却未必能恢复跨块组合出的路径。底层数据同样是“集合”，并不保证任意查询都可按块合成。

推论与应用

前 $n$ 次成功新键插入中，第 $i$ 层至多构建 $\lfloor n/2^i\rfloor$ 次，所以总重建工作为

O\!\left(\sum_{i=0}^{\lfloor\log_2n\rfloor} \left\lfloor\frac n{2^i}\right\rfloor R(2^i)\right).

若固定 $c\ge0$ 且 $R(s)=O(s\log^c(s+1))$ ，摊还分析给每次插入 $O(\log^{c+1}(n+1))$ 。特别地，线性归并每层只收常数摊还费用，全部层合计对数；某次长进位仍可搬动线性多个键。

若答案属于可逆群，且删除对象确实来自当前集合，可考虑分别记录插入与删除贡献再相减；普通成员关系的逻辑或没有这种逆运算。墓碑方案则必须让查询识别已删除身份，并控制清理成本。

完整字典还需决定重复插入、覆盖更新和删除失败的语义。若把同一键的多个版本放进不同块，原先的“不交键集合”不变量已经改变，应改用记录身份并按版本规则筛选，重新证明查询组合。全局重建可以定期清理这些历史记录；逐操作最坏延迟则还需为各层迁移安排预算与期限。

参考资料

Jon Louis Bentley、James B. Saxe，Decomposable Searching Problems I: Static-to-Dynamic Transformation，Journal of Algorithms 1(4), 1980，pp. 301–358。
Mark H. Overmars，The Design of Dynamic Data Structures，Lecture Notes in Computer Science 156，Springer，1983。