块状链表的长度（GPT 重制版）

2026-09-08

本文完全由 GPT 5.6 sol 直接生成，改进了原博客 块状链表的长度 的证明，并给出了更强的结论。

0. 引入

块状链表就是一个链表，每个节点指向一个空间大小为 的数组。一个链表长度为 ，数组空间大小为 的块状链表能装至多 个元素。

给定参数 ，在块状链表中查找一个元素的复杂度是 ，朴素插入和删除一个元素的复杂度是 。

接下来考虑如下维护策略：

我们希望控制 与总元素数量 的关系。

对于 ，实际上可以得到如下精确的上界：

并且这个界可以取到。

特别地，

其中常数 不可改进。

1. 最坏情况

先构造一个例子。

通过不断插入，可以得到

取奇数位置的节点，把它们不断删除到只剩一个元素：

删除过程中不会发生合并，因为这些节点旁边都有一个满块。

然后对所有大小为 的块再插入一个元素，使它们发生分裂。

记分裂出的两个块大小为 ，则

于是得到

假设一共有 个原来的满块，那么

而元素总数为

所以恰好有

这提示我们真正应该证明的是

事实上，更强的结论成立：这个不等式对链表的任意连续区间都成立。

2. 区间不变量

给大小为 的节点定义权值

对于链表上的一个连续区间 ，定义

如果 中有 个节点、 个元素，那么

于是

等价于

接下来证明：

定理：任何时刻，对于任意非空连续区间 ，都有

2.1 两个简单事实

首先，一个满块的权值为

因此，如果一个区间中包含一个满块：

其次，设两个相邻节点大小为 。如果从 中删除一个元素以后不能和 合并，那么

所以

这两个节点原来的总权值至少为

如果一个区间包含这两个节点，左右两段各自最多亏损 ，因此整个区间的权值至少为

这个下界恰好足够支付一次删除造成的 点权值下降。

3. 证明

对操作次数进行数学归纳。

初始链表为空时命题平凡成立。

假设操作前所有连续区间都满足

考虑最后一次操作。

case 1：不产生分裂的插入

一个节点大小从 变成 。

它的权值增加

所以所有受影响区间的权值只会增加。

case 2：产生分裂的插入

一个满块 变成两个节点 ，其中

且

先考虑一个同时包含 的新区间。

把 换回原来的满块，可以得到操作前对应的区间。分裂前后权值之差为

而旧区间包含一个满块，所以旧区间权值至少为 。

因此新区间权值至少为

再考虑一个只包含 中一个的区间。

由于 相邻，被包含的那个新节点一定在区间端点。把它换回满块以后，旧区间中的满块也在端点，所以旧区间权值至少为 。

设新区间包含的节点大小为 。从满块变成 后，权值下降

又因为

对于 有

所以新区间权值至少为

case 3：删除后不发生合并

如果新区间只包含被删除的节点，那么这个节点非空，所以大小至少为 ，其权值至少为

否则，新区间至少还包含被删除节点的一侧邻居。

由于删除后没有发生合并，这两个相邻节点在删除前的大小之和至少为 。

由前面的结论，旧区间权值至少为

删除一个元素使权值下降 ，因此新区间权值至少为

case 4：删除后发生合并

假设两个节点大小为 ，删除一个元素后合并成大小为

的节点。

操作前这两个节点总权值为

操作后为

两者之差为

也就是说，删除并合并以后，所有相关区间的权值反而增加了 。

case 5：删除后节点为空

大小为 的节点权值恰好为

删除这个节点以后，跨过这个位置的区间相当于去掉了一个权值为 的节点，所以权值增加 。

命题保持。

证毕。

4. 结论

取整个链表作为区间，有

因此

而第 1 节构造出的状态满足

所以这个界可以取到。

因此固定 时，这种维护策略能保证的最坏平均节点大小恰好趋于

对应的最坏空间利用率趋于

当 时，

所以不存在 和常数 ，使得

恒成立。

如果用这个上界估计插入、删除复杂度，那么

把 暂时看成实数，最优点约为

渐近上仍然有

5. 一个推广

上面的证明实际上没有真正用到“尽可能均分”，只用到了分裂后较小的节点不能太小。

考虑更一般的策略：

令

用完全相同的证明，对任意连续区间中的 个节点和 个元素，都有

因此

原来的策略中

对于 ，

所以

这里还能看出，“均分”其实比需要的条件更强。

只要每次分裂以后两个节点都至少有

个元素，就仍然可以得到完全相同的最坏情况上界。

例如 时，即使允许

这样的分裂，也仍然有

所以从节点数量的最坏情况来看，- 分裂并不是必要的。

另一方面，无论怎么二分，一个满块溢出以后两个新节点总共都只有 个元素。因此仍然可以形成

这样的结构，每三个节点只有 个元素。

所以如果只允许 split 和“能装下才 merge”，最坏利用率就无法突破约 。

要继续提高这个下界，需要在删除后允许从邻居借元素或重新分配元素，而不能只做 merge。