对数方法动态化

模型与不变量 ​

设静态集合结构在 $s$ 个元素上构建需 $P(s)$ 时间、查询需 $Q(s)$。动态结构维护块 $B_0,B_1,\dots$，其中 $B_i$ 要么为空，要么恰含 $2^i$ 个元素；同一层至多一个块，所有非空块互不相交且并为当前集合。层占用位正是元素数的二进制表示。

插入、查询与摊还代价 ​

插入单元素块后，若第 $i$ 层已有块，就合并两块并用其 $2^{i+1}$ 个元素重建第 $i+1$ 层，像二进制进位一样继续。查询必须访问至多 $\lfloor \log n\rfloor +1$ 个块，并把各块答案用问题允许的组合运算合并，故成本为 $O(Q(n)\log n)$ 的粗界。

一个元素每升到第 $i$ 层只参与一次该层重建。前 $n$ 次插入中，第 $i$ 层发生 $O(n/2^i)$ 次重建，所以总重建成本

$$O(\sum _{i\le \log n}\frac{n}{2^i}P(2^i)).$$

若 $P(s)=O(s{\log }^{c}s)$，摊还插入为 $O({\log }^{c+1}n)$。

有序数组例子 ​

把静态结构取为有序数组。第 0、2 层非空意味着集合由一个单元素数组和一个四元素数组组成；新插入先与第 0 层归并，再可能继续与第 1、2 层进位。成员查询在每个数组二分，因此为 $O({\log }^{2}n)$，而合并排序数组是线性的，摊还插入为 $O(\log n)$。

适用边界与辨析 ​

方法要求查询对不交块可分解：成员关系取 OR、计数取和都可行，但“全局第二短路径”之类答案未必能由块级答案恢复。删除可用墓碑和周期重建，或维护正负结构，但重复键、稳定身份和墓碑抵消必须另定语义。它与全局重建公理库全局重建Global rebuilding在坏度量越界时从活动元素重建结构，并把线性成本收费给足够多次更新。都把昂贵工作分摊到更新上；本页用多层二进制块，后者通常维护一对整体版本。

删除与查询组合 ​

若查询答案形成可逆群，可另建插入结构 $I$ 与删除结构 $D$，查询取 $I$ 的答案减去 $D$；只有幺半群而无逆元时，这种做法不成立。墓碑方案则在每块查询时过滤已删身份，墓碑过多后整体重建。两者都说明“支持插入的动态化”不自动等于完整动态字典。

对 reporting 查询，每块返回结果后还需合并去重，成本至少包含总输出 $k$；若同一逻辑元素因更新出现在多块，必须以版本号选最新记录。并行查询各层可降低墙钟时间，却不改变总工作和层数因子。

一次进位的完整账本 ​

假设当前已有大小 $1,2,4$ 的三个有序块，插入键 13 时先形成大小 1 的临时块。它与原大小 1 块归并成 2，再与原大小 2 块归并成 4，最后与原大小 4 块归并成 8；旧块只有在新块构建完成后才退役。若每次合并都保持稳定次序，重复键还需携带唯一序号，才能让删除或返回原记录保持确定。

一个元素每进入更高层，所在块大小至少翻倍，所以在规模达到 $n$ 前至多被重建 $\lfloor {\log }_{2}n\rfloor +1$ 次。对线性构建 $P(s)=\mathrm{\Theta }(s)$，前 $n$ 次插入的总重建工作满足

$$\sum _{i=0}^{\lfloor \log n\rfloor }\lfloor \frac{n}{2^i}\rfloor P(2^i)=O(n\log n),$$

故每次插入摊还 $O(\log n)$。这个账本解释的是总成本，不承诺某次长进位的尾延迟；若要求最坏延迟，必须增量化每层归并。

参考资料

• Jon Bentley, James Saxe, Decomposable Searching Problems I: Static-to-Dynamic Transformation, Journal of Algorithms, 1980.
• Erik Demaine, MIT 6.851 Advanced Data Structures, static-to-dynamic transformation notes.