跳表实际上是一个多层链表，每一层链表都有序。从下到上（层数从小到大），链表逐渐变小。一个元素位于第 $k$ 层的概率是 $p^k$，实践中一般会限制层数。

因此 $n$ 个元素的跳表的第 $k$ 层链表的大小期望是 $np^k$，呈指数级下降。这保证复杂度正确。

对于实践，我们对每一个节点，维护它的值以及它在每一层的链表指针 nxt[]。

接下来考虑操作。

最基本的操作是在跳表中查找一个节点。由于每一层链表有序，并且越高层节点越少，我们可以从最高层开始遍历。由于在高层的节点一定也在低层，并且每一层链表都具有单调性，所以这个算法正确。

考虑复杂度。显然的，如果证明了搜索的复杂度正确，跳表的其他一系列操作复杂度都正确。

注意到，搜索某个节点，实际上就是从 rank $1$ 走到 rank $k$ 的过程。与朴素链表不同的是，跳表允许不连续地从 $1$ 走到 $k$，这就是它节省的复杂度。

有一个比较简单的感性证明。考虑在第 $k$ 层，rank $i$ 走到 $rank j$ 的期望代价是 $(j - i) p^k$（二项分布），这个代价随着层数增加而减小。

严格证明可以看 OI Wiki，但是我觉得我这个感性就比较够了。

然后考虑更多的操作。考虑插入一个节点。我们需要决定把这个节点到前多少层，这可以随出来。我们找到这些层上这个节点的前驱，就可以按照链表的方法，把它插入到跳表中。删除一个节点同样简单，前驱后继也很基本。

第 $k$ 大和查排名不出所料地需要维护信息。

维护啥？如果能维护出每个节点的 $rank$，那就跟玩一样了。虽然我们显然办不到，但是我们可以维护每一层上相邻两个节点之间的实际距离，也就是排名差。

这个玩意儿是很好维护的。插入的时候我们将后继的排名差加一，删除的时候减一即可。于是我们做完了。

好吧，这个东西好像不那么好维护，但是我现在不太感兴趣了。我打算用 Rust 写一个类似 Redis 的内存数据库，主要是为了练习 Rust。