全局重建

范式与收费 ​

结构维护规模 $n$ 与坏度量 $b$，当负载、墓碑比例或深度越过阈值时，用 $R(n)=O(n)$ 时间从活动元素重建。要得到摊还 $O(1)$ 额外成本，相邻重建点之间必须发生 $\mathrm{\Omega }(n)$ 次可收费更新。

阈值需要迟滞。数组装满时扩为两倍，只在利用率降到 $1/4$ 时缩半；若在 $1/2$ 上下同时扩缩，一次插入和一次删除就可能来回触发 $\mathrm{\Theta }(n)$ 重建。几何间隔既防抖，也提供付款操作。

墓碑哈希表 ​

开放定址表删除键时留下墓碑，直接清空会截断其他键的探测链。活动负载超过 $2/3$ 时扩容，墓碑比例过高时按当前活动规模重建：扫描旧表、复制活动键并重选哈希参数。增量重建期查询须查新旧两表，后续插入写入新表。

静态有序数组也可维护成二进制层级：每层至多一个大小 $2^i$ 的数组，同层冲突归并进位。插入摊还良好，但查询需二分所有非空层，不能只报告更新成本。

失效条件 ​

若清理还要扫描与活动规模无关的无界历史日志，按 (O(n)) 收费就不足。全局重建也不等于去摊还化公理库去摊还化Deamortization把偶发的大工作拆成有预算的增量步骤，使逐操作延迟获得最坏界。：stop-the-world 版本仍有一次线性停顿，只有增量执行并证明迁移追得上更新，才有逐操作界。

势能可取为距下次阈值已积累的更新量：普通更新增加常数势，重建释放 (\Theta(n)) 势支付扫描；扩缩后势必须非负。二进制层级动态化还会让查询跨 (O(\log n)) 个静态块，若单块查询为 (Q(n))，一般得到 (O(Q(n)\log n))，更新改善不自动保留静态查询界。

阈值若依查询延迟或墓碑分布而非一个单调坏度量变化，相邻重建之间未必有足够操作付款。此时要么换用局部维护，要么给触发指标另建势能，不能沿用几何容量的账。

从触发到发布的完整过程 ​

重建开始时先冻结活动集合的逻辑快照，计算新容量与参数；随后遍历旧结构，只把仍活动元素插入新结构；最后验证计数、切换根指针并回收旧存储。Stop-the-world 版本把四步作为一次操作，增量版本则要保留更新日志并让查询访问两个版本。选择哪一种决定的是最坏延迟，不改变重建恢复的目标不变量。

开放定址例子中，若表长 16 有 8 活动键、5 墓碑，重建逐个重新探测，而不是把槽位原样复制；新哈希函数会改变每个键的位置。完成后验证活动计数为 8、每键可达、墓碑为零，才可发布。若中途插入键 $x$，应直接插新表并防止旧扫描再次复制旧版本 $x$。

几何阈值的证明 ​

扩容后负载至多约 $1/2$，再次达到满阈值至少需 $\mathrm{\Omega }(n)$ 次插入；缩容后负载至多 $1/2$，再次跌到 $1/4$ 也需 $\mathrm{\Omega }(n)$ 次删除。每次操作存常数信用，总信用支付 $O(n)$ 复制。若扩与缩都以 $1/2$ 为边界，两个操作即可往返，收费证明失效。

层级静态化中，第 $i$ 层每发生一次重建就合并 $2^i$ 项，而每 $2^i$ 次插入至多触发一次，因此该层对每次插入收费 $O(1)$；跨 $O(\log n)$ 层得到摊还 $O(\log n)$。

何时不用全局重建 ​

局部旋转能持续维护平衡时，全局扫描会制造不必要停顿；数据量超过内存时，重建还会产生外存 Sort/Scan 成本。全局重建适合坏度量能长期积累且一次清理恢复良态的结构，不适合每次更新都可能破坏查询正确性的约束。

参考资料

• Jon Bentley, James Saxe, “Decomposable Searching Problems I,” J. Algorithms, 1980.
• Mark Overmars, The Design of Dynamic Data Structures, 1983.
• Cormen et al., Introduction to Algorithms, 4th ed., Ch. 16.