一颗奇怪的树

· · 个人记录

找了一堆关于 Finger tree 的 blog，但是根本看不下去，只看懂了大概的方法。于是我来说一下。

我们如果要维护一个数据结构，支持以下操作：

怎么快速做？

如果只有操作一，显然可以用双向链表完成。但是操作二就没法快速做了，寄！

平衡树！我们可以拿下标当主键，头尾加入相当于加入新数，操作二相当于第 k 大…… 然而平衡树常数太大，我卡你常！

那我们就要考虑考虑了……

想一想能不能用倍增做。

我们维护 prv 和 nxt，指向当前位置前后的第 2^i 个位置。如果它们可以维护，操作二就可以对数做。

考虑在头加入，不会更改它后面任意的 nxt，只会更改 pre。一个数的 pre 如果是新头，就意味着它到新头的距离是 2^i。我们用旧头的 nxt 去跳，然后来更新。同时，我们可以简单地更新 nxt。

在尾加入是同理的。

于是我们就有了一个基于倍增的，常数应该小得多的实现。

…… 很好！但是，deque 做这些操作是 O(1) 的！

所以我们要想办法做任意位置插入。

Finger tree 还是不会……但是感觉常数应该比这个大罢（心虚）。