关于 skip list 的一些扩展想法

本文同步发表于我的个人博客，应该有更好的阅读体验

写这个有啥用啊

0 创作背景

最近碰到了一些需要高效实现 单点删除单点插入区间查询最小值 的题目，感觉一般的平衡树已经满足不了我了。

于是决定整点阴间跳表，刚好以前嘴巴过一个区间操作的跳表，上网搜了一下，又在 2009 的冬令营论文里面发现了这玩意儿。

于是就整合顺便扩展了一下，感觉实现起来会比一般的平衡树简单很多，希望能在 OI 实战中有点用处。

假装你们都会跳表了，我们直接从扩展开始。

1-0 超越平衡树

首先我们知道，最朴素的跳表能干的事儿基本上就是 std::map 能干的事儿。

因此首先我们得超越 std::map ，怎么说得和最普通平衡树平起平坐吧。

发现我们离普通平衡树的差距就在于 kth 和 rank 这两个操作，我们先考虑看起来阳间一点的 rank。

考虑把每一个点的权值置为 1，那么 rank 本质上就是起点到当前点的区间和。

由于跳表的结构类似于倍增，因此我们先把一个不修改的跳表看作一个倍增的结构。

而我们带权倍增，来求一些区间信息的时候，一般就是对于一个节点，记录他跳到的终点与当前点之间那些点的贡献。

仔细想想，发现这里也可以这么搞。

我们考虑对于每一个节点的每一层维护它到下一个与它高度相同的点之间的信息，这里就是点数。

然后我们考虑不断去跳，不难发现我们这里顺路把权值加上的话，复杂度和普通的跳表是完全一致的。

然后我们考虑单点修改，不难发现插入删除的时候都只会修改 O(\log n) 个节点，每层刚好一个。

其实也就是后继改变了的那些节点，因此复杂度还是 O(\log n) 的。

然后仔细想想，我们带权倍增的时候可以用类似线段树上二分的写法，实现在一个单调的序列里找到某一个权值的位置，和树上 k 级祖先的倍增解法比较类似。

因此这里直接在刚才的基础上，看跳完之后到达的节点的 rank 是什么一个情况就行，重合了就可以跳出了。

于是就实现了 rank 和 kth，复杂度是 O(\log n) 的，已经可以通过普通平衡树了。

1-1 维护区间信息

其实不难发现，上面的 rank 操作的实现过程还顺带实现了单点修改区间查询，和树状数组其实比较类似。

考虑区间和等可差分的信息已经可以通过类似的方法进行查询了，但是不可差分的信息就比较难搞。

其实也不要紧。

假设我们查询的是区间 [l, r] ，干脆以 RMQ 举例好了。

考虑从最高层开始跳，要是跳一步跳进 [l, r] 了那就以这个节点为起点想两边扩展，不难发现这里就不需要差分了，还是 O(\log n) 的，毕竟前驱后继什么的本来就应该是要维护的。

考虑如果没跳到，那么就降一层继续试，这么跳的话复杂度应该也是 O(\log n) 的。

那么就可以实现不用差分的区间查询了。

感觉其实和猫树的思想比较相似？

1-1.5 维护区间信息ex

然后这个 DPair 就去看了看论文并且得到了一种更为方便的实现方式。

注：个人根据自己的理解稍微改造了一下，想看原论文写法的可以自己去找，附件当中有参考实现。

大概是这样的，考虑对于每一次询问 [l,r]，首先我们要遍历尽可能少的节点来完整覆盖这个区间，因此我们考虑从 root 节点的最高层开始向右遍历。

考虑往右遍历时，当前节点可能会有以下几种情况：

• 左端点 > r，此时显然这个节点及这个节点所有的下层节点都不可能在这个区间内了，因此可以直接弹出。
• 右端点 <l，此时显然这个节点的后继还可能有前途，因此直接搜当前节点的后继并返回那个节点的搜索结果即可。
• 右端点 > r，这时我们向下搜索这个节点的下层节点即可，然后返回那个节点的搜索结果。
• 左端点 <l 且右端点在 [l,r] 内，考虑这个节点的后继和下层都可能产生贡献，因此把这两部分加起来即可。
• 左右端点均在 [l, r] 内，由于我们搜索到了当前节点，那么这个节点一定就是产生贡献的一个节点，因此返回这个节点维护的信息和它的后继维护的信息即可，并且为了避免重复贡献，我们可以考虑在返回结果时，把区间的右端点移动到这个这个节点的前一个位置。

具体实现时可能不尽如此，但是手推一下然后排除算重的情况的话还是方便的。

其实仔细思考会发现这个东西和上面查询的具体节点是完全一致的，因此复杂度是相同的，而且好处在于不需要通过前驱来向前跳，而且是单向的，可能会对常数有一定的优化。

不过反正怎么说都要靠维护前驱来完成删除操作，因此上面那个写法并不会逊色太多？

1-2 一些奇怪的东西

我们感性理解一下，假设我们加层的概率是 \frac{1}{2} ，那么就可以考虑把原跳表看成每一个节点期望有两个儿子的一个结构，那么其实这就是一个线段树的结构。

考虑这个阈值变为 \frac{1}{4}，那么这就是一个四叉的线段树。

考虑把阈值变为 \frac{1}{\sqrt{n}}，那么就得到了一个分块，或者说块状链表，甚至可以考虑用 std::vector 实现。

如果不同层的概率不同，我们可能可以得到类似 sqrt-tree 或者底层分块后的线段树的结构。

所以仔细想想这东西还是挺 nb 的。

1-3 两种实现

就我目前所知，跳表应该有两种实现方式：

• 比较简单易懂的一种：就是构建一个链表，每一个节点上维护一个数组，表示当前节点每一层具体是什么东西，这样比较方便随机访问一个特定的节点，朴素实现可能需要 O(n\log n) 的空间，但实现略精细些就可以 O(n) 空间，个人没实现过。
• 个人实现过的一种：把每一个节点的每一层都看作一个新的节点，记录这个节点的下层节点，后继节点和层号，这种实现方式比较方便，不易出错，而且显然 O(n) 空间。

具体哪种更好本人没有尝试过，但是至少第二种实现已经在模板题里吊打 FHQTreap 了。

2-0 也许可以区间修改？

仔细想想，跳表的结构既然可以和这么多数据结构相似，那么用类似的方法去打标记是不是也比较可行？

首先我们考虑单点查询。

不难发现，我们在刚才的区间查询当中，找到了一些节点使得这些节点可以完全覆盖一个区间，那么这里我们考虑给这些节点打上一个永久化的标记。

那么按照原先我们在线段树上标记永久化的思想，我们现在只需要想办法在查询到某一个节点时，能够顺便遍历到所有包含它的节点。

首先发现这些节点每层一个。

其次发现我们直接检索这个节点，每一层被访问到的最后一个节点就是我们要找的点。

然后考虑插入删除，不难发现删除是可以直接删除的，插入的话把沿路的标记的贡献减掉就变成了普通的插入。

不难发现这样的话值都是对的。

因此，我们可以实现区间修改单点询问。

2-1 区间查询才是正道！

然后我们要看看能不能实现区间修改区间查询。

我们先假设没有插入删除等结构变化的操作。

那么不就是一棵结构略奇怪些的线段树嘛，这不随便做都可以。

然后考虑带上结构变化。

考虑插入删除的时候，会把包含对应的节点所有区间的标记都下传一遍，其实就是动态结构的线段树了。

然后仔细考虑区间修改的时候我们访问的东西，不难发现只要结构是确定的，我们访问到的点就一定是确定的，我们就一定可以把所有需要下传的标记按顺序下传，和线段树非常类似。

实现起来可能会略麻烦些。

2-2 文艺平衡树？

我们现在已经可以实现区间修改，区间查询，单点插入删除了，但是我们还有一个没有超越平衡树的地方。

那就是区间翻转。

我大概嘴巴了一下，应该有一个这样的做法：

首先我们一开始是对于每一个点维护后缀的答案，我们这里前后缀都维护。

然后每一个点打一个标记表示是否被翻转，这个标记是永久化的。

这样的话我们每一次修改就只有 O(\log n) 个节点，剩下的节点用区间修改的套路打上标记即可。

然后就可以实现区间翻转了，但是估计细节会很多。

3 块状链表的另一种解释？

大家都知道块状链表是什么吧。

考虑一个两层，以 O(\frac{1}{\sqrt{n}}) 的概率加层的跳表其实就是一个分块的结构。

由于是动态的，那么它就是一个功能类似块链的东西，我们暂且称之为 “块状跳表”。

而且，其实我们完全可以根据不同的层设计不同的操作不是吗？

我们随便找一道块链的经典题好了，就决定是你了，带插入区间 k 小值！

对于这道题，我们可以建立块状跳表我们可以考虑对于一个 level=2 的节点，然后在上面开一个值域分块，然后考虑取一个前缀和。

那么每一次都只有 O(\frac{1}{\sqrt{n}}) 的概率需要进行一次 O(n) 的前缀和重构，所以这部分是 O(n\sqrt{n}) 的。

然后已知前缀和，我们就可以检索出首尾节点然后用类似最初分块的方法去做了。

朴素实现的块链似乎还要判块长 > \sqrt{n} 就重构什么的，用块状跳表似乎就不用考虑这些奇奇怪怪的东西。

唯一的缺点是不能用 vector 优化了，导致被块链吊打（大悲）

4 总结

今年戳赛考过四毛子了，明年戳赛考个跳表说这是链表不过分吧。

其实仔细思考一下跳表，会发现这就是一些常见的结构动态化之后的结果，所以如果加上分层讨论的话，可能可以实现不少结构的动态化。

另外，以上全是口胡，实际运行效率和实现难度甚至正确性我都不知道。

不过要是我实现之后发现实现难度低的话，那么把这玩意儿在 OI 中推广一下其实也不是不可以吧。