发布于 ，更新于 

手把手带你实现跳表

引入

跳表（跳跃表）能够维护一个数的集合（作用类似普通平衡树），查找时间复杂度为 \(\Theta(\log n)\)，与平衡树一样基于链表结构。由于不需要平衡树那么多旋转什么的，所以效率比较高，一般认为性能能打红黑树。除此以外，链表的特性使它能够以线性时间遍历某个子段。Redis 的有序集合就是用跳表实现的。

更简单来说，跳表是一个支持 \(\Theta(\log n)\) 时间随机访问的链表。

定义

上面这个东西叫链表。

我们知道，链表只支持线性时间访问，所以不能二分。我们如果想维护一个有序序列的话，虽然插入删除很快，但是找到一个值对应的位置很慢。

我们又知道，链表的访问形式实际上是一个一个遍历，而它有 \(n\) 个元素，这是它 \(\Theta(n)\) 复杂度随机访问的根源所在。

那我们是不是可以给链表精简一下呢？比如说，我给链表多加几层，每层减少一半的元素，像这样：

（蓝色方框括起来的是一个节点，实现的时候我们不需要把上面几层显式地建出来，只需要创建对应层的指针即可。）

这样的话，我就能像上图这样找到 \(78\) 这个节点了。

橙色路径是原有路径，走了 \(4\) 次。而上面的绿色路径只走了 \(\log_2 4 = 2\) 个次。好好好，那我这样建的话，我就能在链表上二分了！
实际上这个东西叫完美跳表。

跳表分两种，一种是上面的完美跳表（暂且这样叫）。这个东西最大的特点就是过于理想化了。如果加上插入删除的话，维护对应层的指针就太难了，每次都得更新。

另一种是基于随机化的跳表。
要随机化的东西叫做 \(level\)。一个跳表节点的 \(level\)，代表着这个节点同时存在于 \(1 \sim level\) 层的链表中。比如说，上图的值为 \(1\) 的节点 \(level = 3\)，值为 \(23\) 的节点 \(level = 1\)。
取 \(level\) 的方式类似于抛硬币，计算 \(level\) 时，如果硬币正面朝上，就 \(+1\) 并继续抛；如果反面朝上，则停止。通过这样定下节点 \(level\) 的跳表就是我们今天要实现的跳表。

基本实现

为了方便演示，这里就不再封装跳表了，其实跟着教程一边走一边封装也是可行的。

一些变量

int level 记录跳表的最高 level。

Node head 为了防止过多的边界的分类讨论，建立一个空结点当头节点。

节点

动态分配内存太慢了，如果用动态分配的，我还不如直接 STL。

所以开好数组作为预分配的空间，然后我们可以开一个指针记录分配到了哪一个位置。需要创建新节点的时候直接返回一个 ++tot 即可。

1
2
3
4
struct Node {
    int key, level;
    Node* nxt[MAX_LEVEL];
} space[N], *tot = space;
注意

此处 level 的含义是：该节点存在于 0 到level-1 层的链表中，与前文定义 1 到 level不同。

垃圾回收可以自己实现，待会的整体演示里面会放。

分配一个新节点空间，返回新节点的指针：

1
#define new_node() (++tot)

创建一个值为 key 高度为 level 的节点：

1
2
3
4
5
6
Node* create_node(int level, int key) {
    Node* res = new_node();
    res->level = level;
    res->key = key;
    return res;
}

随机生成 level

前面说了，是抛硬币。

所以我们可以直接借用一些随机数生成器1。

然后我们肯定不能让层数无限大啊，所以需要设置一个 MAX_LEVEL 作为最大层数。

1
2
3
4
5
6
7
8
9
10
11
12
#define MAX_LEVEL 12

std::random_device seed;
std::minstd_rand rng(seed());

int random_level() {
    int res = 1;
    while (res < MAX_LEVEL && (rng() & 1)) {
        ++res;
    }
    return res;
}

插入节点

声明：

1
void insert(int key);

三步走：找到需要插入的位置，插入节点，更新对应 level 的链表。

首先我们直接从高 level 开始跳，跳不了了就跳低一级的 level 即可找到需要插入的位置。
同时记录每一个 level 的当前位置之前的节点。（即可能需要更新后向指针的节点）。

1
2
3
4
5
6
7
Node *cur = head;  // current

for (int lev = level - 1; lev != -1; --lev) {
    while (cur->nxt[lev] && cur->nxt[lev]->key < key)
        cur = cur->nxt[lev];  // 存在满足要求的点就跳
    update[lev] = cur;
}

细节：可能当前 level 还没有到跳表可能达到的最高 level，但是当前这个节点随机到的 level 值在这两个数中间，所以需要将 level 到 MAX_LEVEL 这段补全为 head：

1
2
3
4
5
6
7
int lev = random_level(); // 当前节点的 level 值
if (lev > level) {
    for (int i = level; i < lev; ++i)
        update[i] = head;

    level = lev;
}

创建节点：

1
cur = create_node(lev, key);

执行插入操作，即对于每一层链表，更新前一个节点的指针，并让当前节点的后向指针指向后一个节点。

1
2
3
4
for (int i = lev - 1; i > -1; --i) {  // 普通链表插入操作
    cur->nxt[i] = update[i]->nxt[i];
    update[i]->nxt[i] = cur;
}

删除节点

和插入类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void erase(int key) {
    nodePointer cur = head;  // current

    for (int lev = level - 1; lev != -1; --lev) {
        while (cur->nxt[lev] && cur->nxt[lev]->key < key)
            cur = cur->nxt[lev];  // 存在满足要求的点就跳
        update[lev] = cur;
    }

    cur = cur->nxt[0];
    for (int i = 0; i < level; ++i)
        if (update[i]->nxt[i] == cur)
            update[i]->nxt[i] = cur->nxt[i];
        else
            break;

    while (level > 1 && !head->nxt[level - 1])  // 更新当前最大层数
        --level;
}

额外要注意的是，可能跳表的最高层就这一个节点，删了就没了，所以要判断并更新最大层数。

查找结点

实际上上面两个函数的第一部分就相当于查找。

1
2
3
4
5
6
7
8
9
bool find(int key) {
    Node* cur;

    for (int lev = level - 1; lev > -1; --lev)
        while (cur->nxt[lev] && cur->nxt[lev]->key < key)
            cur = cur->nxt[lev];  // 存在满足要求的点就跳

    return cur->nxt[0] ? cur->nxt[0]->key == key : false;
}

查找前驱后继的方法也差不多，前驱就是查找后直接返回 cur 而不是 cur->nxt[0]，后继可以跳到 cur->nxt[lev]->key <= key 的位置之后返回 cur->nxt[0]->key。最后的代码中有体现。

随机访问

上面其实已经实现了跳表的基本功能了，但是显然，目前实现的功能都可以用平衡树替代，而且平衡树还能够按照数的排名查询。

由于维护的是有序序列，所以按照数的排名查询相当于随机访问。

接下来我们来实现跳表的随机访问。具体方法：维护每个后向指针的“跨度”（span），即它跳了几个节点。

形式化定义

设指针 \(ptr\) 从第 \(a\) 个节点指向第 \(b\) 个节点，则 \(ptr\) 的跨度为 \(b-a\)

除此以外，我们还需要维护一个长度 length，在每次 erase 和 insert 的时候加减一下就好了。

重写智能指针

啥是智能指针？不太清楚，但是我感觉维护一个 span 的指针实在太智能了！

我们需要给指针记录一个“跨度”，那就维护一个结构体作为指针，存原来的裸指针和跨度。

总的来说，需要构造函数并重载一个运算符，一个类型转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct nodePointer {
    int span;
    Node* pointer;
    nodePointer() {
        this->pointer = nullptr; // 构造函数，将指针初始化为空
    }
    nodePointer(Node* node) {
        this->pointer = node;  // 如果提供了指针就用提供的
    }
    Node* operator->() {
        return pointer; // 指针原有的箭头运算符，访问 nodePointer->x 相当于访问 pointer->x
    }
    operator Node*() const {
        return pointer; // 智能指针转换为裸指针，直接返回 pointer 就好了
    }
};
注意

不要在所有地方都使用nodePointer，我们只在需要维护跨度的地方使用就好了。
编写代码时一定要注意类型的使用，比如说 unsignedlong 不应乱用之类的。如果错误地更新span，而你滥用了nodePointer，可能就没那么容易找到问题了。

博主因为滥用 unsigned，跳表调了两天多。

需要维护跨度的地方只有跳转用的指针，即 nxt[]。

更改后的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Node {
    int key, level;
    struct nodePointer {
        int span;
        Node* pointer;
        nodePointer() {
            this->pointer = nullptr; // 构造函数，将指针初始化为空
        }
        nodePointer(Node* node) {
            this->pointer = node;  // 如果提供了指针就用提供的
        }
        Node* operator->() {
            return pointer; // 指针原有的箭头运算符，访问 nodePointer->x 相当于访问 pointer->x
        }
        operator Node*() const {
            return pointer; // 智能指针转换为裸指针，直接返回 pointer 就好了
        }
    };
    nodePointer nxt[MAX_LEVEL];
} space[N];
using nodePointer = typename Node::nodePointer; // 为了方便书写，缩一下

重写插入函数

开一个数组记录每一层“上一个节点”的位置（利用跨度）。

1
int lst_pos[MAX_LEVEL];

然后在函数开头找位置的时候顺便把它处理出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int lev = level - 1; lev > -1; --lev) {
    // 更新 lst_pos
    if (lev == level - 1)
        lst_pos[lev] = 0; // 默认得是 0
    else
        lst_pos[lev] = lst_pos[lev + 1]; // 否则从上一层继承

    while (cur->nxt[lev] && cur->nxt[lev]->key < key) {
        lst_pos[lev] += cur->nxt[lev].span; // 更新
        cur = cur->nxt[lev];  // 存在满足要求的点就跳
    }
    update[lev] = cur;
}

插入的时候计算一下就好了。如图：

然后 level 大于这个节点的指针跨度要加一。

结合代码理解。

1
2
3
4
5
6
7
for (int i = 0; i < lev; ++i) {  // 普通链表插入操作
    cur->nxt[i] = update[i]->nxt[i];
    update[i]->nxt[i].pointer = cur; // 这里不要直接让 nxt[i] = cur，因为后面还要用到 nxt[i].span
    cur->nxt[i].span = update[i]->nxt[i].span - (lst_pos[0] - lst_pos[i]); // lst_pos[0] 实际上就是上一个节点的位置
    update[i]->nxt[i].span = lst_pos[0] - lst_pos[i] + 1;
}
for (int i = lev; i < level; ++i) ++update[i]->nxt[i].span; // 维护高于新节点的指针的跨度

别忘了 ++length。

重写删除函数

把要删掉的指针的 span 加起来赋值给新指针就好了。

和 insert 一样，别忘记比当前节点高的指针跨度要 -1。

1
2
3
4
5
for (int i = 0; i < level; ++i)
    if (update[i]->nxt[i] == cur)
        update[i]->nxt[i].pointer = cur->nxt[i], update[i]->nxt[i].span += cur->nxt[i].span - 1;  // 跨度直接扔给前面那个指针就行了
    else
        --update[i]->nxt[i].span;

随机访问（按照排名查询）

1
2
3
4
5
6
7
8
9
10
int findrk(int k) {
    assert(k <= length && k); // k 不满足要求就异常
    Node* cur = head;
    for (int lev = level - 1; lev > -1 ; --lev)
        while (cur->nxt[lev] && k - cur->nxt[lev].span > 0) {
            k -= cur->nxt[lev].span;
            cur = cur->nxt[lev];  // 存在满足要求的点就跳
        }
    return cur->nxt[0]->key;
}

微调

我们可以对 MAX_LEVEL 和选取 level 的概率进行微调。

比如说下面的普通平衡树代码，把选取层数的 \(p\) 改成了 \(\frac 14\)，即 (rng() & 1) && (rng() & 1)，MAX_LEVEL 设为了 \(7\)，经测试这样比较快，在无快读不开 O2 的情况下吊打 Splay/FHQ/Treap，加了快读 O2 之后不知道为啥跑不过我之前写的指针 FHQ 了。另外数组 Treap 始终被吊打。这就是指针带给我的自信

后记

实际上跳表最大的优点是能够顺序访问，这点是很多平衡树做不到的，FHQ Treap 分裂区间之后中序遍历是可以的，但是常数太大。

等我把跳表模板题搞出来，他们都得死！

完整代码

含类型泛化和封装成类。

另外实现了一些输入输出操作，自己看应该能看懂了。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <iostream>
#include <random>
#include <cassert>

#include <cstdlib>

using std::cin;
using std::cout;

std::random_device seed;
std::minstd_rand rng(seed());

#define N 106
#define MAX_LEVEL 32

using i32 = signed int;

template <typename T>
class skiplist {
private:
    i32 level;
    struct Node {
        T key;
        i32 level; // 千万的别用 unsigned
        struct nodePointer {
            i32 span; // 这个也千万他妈的别用 unsigned
            Node* pointer;
            nodePointer() {
                this->pointer = nullptr; // 构造函数，将指针初始化为空
            }
            nodePointer(Node* node) {
                this->pointer = node;  // 如果提供了指针就用提供的
            }
            Node* operator->() {
                return pointer; // 指针原有的箭头运算符，访问 nodePointer->x 相当于访问 pointer->x
            }
            operator Node*() const {
                return pointer; // 智能指针转换为裸指针，直接返回 pointer 就好了
            }
        };
        nodePointer nxt[MAX_LEVEL];
    } space[N];
    i32 bintop;
    using nodePointer = typename Node::nodePointer;
    Node *head, *tail, *tot, *rubbin[N / 4 * 3];

#define new_node() (bintop ? rubbin[bintop--] : ++tot)
#define del_node(x) (rubbin[++bintop] = (x))

    Node* create_node(const i32& level, const T& key) {
        Node* res = new_node();
        res->level = level;
        res->key = key;
        return res;
    }

    i32 random_level() {
        i32 res = 1;
        while (res < MAX_LEVEL && (rng() & 1)) {
            ++res;
        }
        return res;
    }

    Node* update[MAX_LEVEL];
    i32 lst_pos[MAX_LEVEL + 1];  // 每个 level 遍历到的最后一个元素的位置

public:
    skiplist() {
        tail = nullptr;
        level = 0;
        head = tot = space;
        bintop = 0;
        length = 0;
        lst_pos[MAX_LEVEL] = 0;
        for (i32 i = 0; i < MAX_LEVEL; ++i)
            head->nxt[i] = nullptr, head->nxt[i].span = 0;
    }

    void insert(const T& key) {
        Node* cur = head;  // current

        for (i32 lev = level - 1; lev > -1; --lev) {
            // 更新 lst_pos，这里由于已经把 lst_pos[MAX_LEVEL] 设为 0 了，所以不需要像上文一样特判
            lst_pos[lev] = lst_pos[lev + 1];

            while (cur->nxt[lev] && cur->nxt[lev]->key < key) {
                lst_pos[lev] += cur->nxt[lev].span;
                cur = cur->nxt[lev];  // 存在满足要求的点就跳
            }
            update[lev] = cur;
        }
        i32 lev = random_level();
        if (lev > level) {
            for (i32 i = level; i < lev; ++i) {
                update[i] = head;
                update[i]->nxt[i].span = length;  // 这层都还没有节点，直接从 head 指向尾部（nullptr），跨度为 length
            }
            level = lev;
        }

        cur = create_node(lev, key);

        for (i32 i = 0; i < lev; ++i) {  // 普通链表插入操作
            cur->nxt[i] = update[i]->nxt[i];
            update[i]->nxt[i].pointer = cur; // 这里不要直接让 nxt[i] = cur，因为后面还要用到 nxt[i].span
            cur->nxt[i].span = update[i]->nxt[i].span - (lst_pos[0] - lst_pos[i]); // lst_pos[0] 实际上就是上一个节点的位置
            update[i]->nxt[i].span = lst_pos[0] - lst_pos[i] + 1;
        }
        for (i32 i = lev; i < level; ++i) ++update[i]->nxt[i].span;

        ++length;
    }

    void erase(const T& key) {
        Node* cur = head;  // current

        for (i32 lev = level - 1; lev != -1; --lev) {
            while (cur->nxt[lev] && cur->nxt[lev]->key < key)
                cur = cur->nxt[lev];  // 存在满足要求的点就跳
            update[lev] = cur;
        }

        cur = cur->nxt[0];
        for (i32 i = 0; i < level; ++i)
            if (update[i]->nxt[i] == cur)
                update[i]->nxt[i].pointer = cur->nxt[i].pointer, update[i]->nxt[i].span += cur->nxt[i].span - 1;  // 跨度直接扔给前面那个指针就行了
            else
                --update[i]->nxt[i].span;

        while (level > 1 && !head->nxt[level - 1])  // 更新当前最大层数
            --level;
        del_node(cur);
        --length;
    }

    bool find(const T& key) {
        Node* cur = head;

        for (i32 lev = level - 1; lev > -1; --lev)
            while (cur->nxt[lev] && cur->nxt[lev]->key < key)
                cur = cur->nxt[lev];  // 存在满足要求的点就跳

        return cur->nxt[0] ? cur->nxt[0]->key == key : false;
    }

    T findrk(i32 k) {
        assert(k <= length && k); // k 不满足要求就异常
        Node* cur = head;
        for (i32 lev = level - 1; lev > -1 ; --lev)
            while (cur->nxt[lev] && k - cur->nxt[lev].span > 0) {
                k -= cur->nxt[lev].span;
                cur = cur->nxt[lev];  // 存在满足要求的点就跳
            }
        return cur->nxt[0]->key;
    }

    i32 length;
};

skiplist<i32> list;

#include <string>

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    i32 n, tx;
    cin >> n;
    for (i32 i = 1; i <= n; ++i) {
        cin >> tx;
        list.insert(tx);
    }
    std::string s;
    while (cin >> s) {
        switch (s[0]) {
            case ('l'): cout << list.length << std::endl; break;
            case ('i'):
            case ('a'):
                cin >> tx;
                list.insert(tx);
                break;
            case ('d'):
            case ('r'): {
                cin >> tx;
                if (list.find(tx))
                    list.erase(tx);
                else
                    cout << "该值不存在" << std::endl;
                break;
            }
            case ('f'):
                cin >> tx;
                cout << (list.find(tx) ? "存在" : "不存在") << std::endl;
                break;
            case ('g'):
                cin >> tx;
                cout << list.findrk(tx) << std::endl;
                break;
            default: cout << "未知命令" << std::endl;
        }
    }

    return 0;
}
普通平衡树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <iostream>
#include <random>

using std::cin;
using std::cout;

using i32 = int;
using i64 = long long;

std::random_device seed;
std::minstd_rand rng(seed());

const i32 MAX_LEVEL = 7;

#define N 100005

struct Node {
    i32 level;
    i64 key;

    struct ptr {
        Node* pointer;
        i32 span;

        ptr() {
            pointer = nullptr;
            span = 0;
        }
        ptr(Node* x) {
            pointer = x;
            span = 0;
        }
        operator Node*() const& {
            return pointer;
        }
        Node* operator->() const& {
            return pointer;
        }
    } nxt[MAX_LEVEL];

} space[N], *rubbin[N];
Node* tot = space;
Node* head = space;
i32 bintop;

#define new_node() (bintop ? rubbin[bintop--] : ++tot)
#define del_node(x) (rubbin[++bintop] = (x))

i32 level;  // global max level now
i32 length;

i32 random_level() {
    i32 res = 1;
    while (res < MAX_LEVEL && (rng() & 1) && (rng() & 1))
        ++res;
    return res;
}

Node* create_node(const i32& level, const i64& key) {
    Node* res = new_node();
    res->key = key;
    res->level = level;
    return res;
}

void insert(const i64& key) {
    Node* cur = head;
    Node::ptr update[MAX_LEVEL];
    i32 lst_pos[MAX_LEVEL + 1];
    lst_pos[level] = 0;

    for (i32 l = level - 1; l > -1; --l) {
        lst_pos[l] = lst_pos[l + 1];

        while (cur->nxt[l] && cur->nxt[l]->key < key) {
            lst_pos[l] += cur->nxt[l].span;
            cur = cur->nxt[l];
        }
        update[l] = cur;
    }

    i32 lev = random_level();

    if (lev > level) {
        for (i32 i = level; i < lev; ++i) {
            update[i] = head;
            update[i]->nxt[i].span = length;
            lst_pos[i] = 0;
        }
        level = lev;
    }

    cur = create_node(lev, key);

    for (i32 i = 0; i < lev; ++i) {
        cur->nxt[i] = update[i]->nxt[i];
        cur->nxt[i].span = update[i]->nxt[i].span - (lst_pos[0] - lst_pos[i]);
        update[i]->nxt[i].pointer = cur;
        update[i]->nxt[i].span = lst_pos[0] - lst_pos[i] + 1;
    }

    for (i32 i = lev; i < level; ++i)
        ++update[i]->nxt[i].span;

    ++length;
}

void erase(const i64& key) {
    Node* cur = head;
    Node::ptr update[MAX_LEVEL];
    for (i32 l = level - 1; l > -1; --l) {
        while (cur->nxt[l] && cur->nxt[l]->key < key)
            cur = cur->nxt[l];
        update[l] = cur;
    }

    cur = cur->nxt[0];

    for (i32 i = 0; i < level; ++i)
        if (update[i]->nxt[i] == cur)
            update[i]->nxt[i].span += cur->nxt[i].span - 1, update[i]->nxt[i].pointer = cur->nxt[i].pointer;
        else
            --update[i]->nxt[i].span;

    while (level > 1 && !head->nxt[level - 1])
        --level;

    del_node(cur);
    --length;
}

i32 get_rk(const i64& key) {
    Node* cur = head;
    i32 res = 0;
    for (i32 l = level - 1; l > -1; --l) {
        while (cur->nxt[l] && cur->nxt[l]->key < key) {
            res += cur->nxt[l].span;
            cur = cur->nxt[l];
        }
    }
    return res + 1;
}

i64 find_by_rk(i32 k) {
    Node* cur = head;
    for (i32 l = level - 1; l > -1; --l) {
        while (cur->nxt[l] && k - cur->nxt[l].span > 0) {
            k -= cur->nxt[l].span;
            cur = cur->nxt[l];
        }
    }
    return cur->nxt[0]->key;
}

Node* prev(const i64& key) {
    Node* cur = head;
    for (i32 l = level - 1; l > -1; --l) {
        while (cur->nxt[l] && cur->nxt[l]->key < key)
            cur = cur->nxt[l];
    }
    return cur;
}

Node* next(const i64& key) {
    Node* cur = head;
    for (i32 l = level - 1; l > -1; --l) {
        while (cur->nxt[l] && cur->nxt[l]->key <= key)
            cur = cur->nxt[l];
    }
    return cur->nxt[0];
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    i32 n;
    i32 op, x;
    cin >> n;
    while (n--) {
        cin >> op >> x;
        switch (op) {
            case (1): insert(x); break;
            case (2): erase(x); break;
            case (3): cout << get_rk(x) << '\n'; break;
            case (4): cout << find_by_rk(x) << '\n'; break;
            case (5): cout << prev(x)->key << '\n'; break;
            case (6): cout << next(x)->key << '\n'; break;
        }
        // cout.flush();
    }

    return 0;
}

复杂度分析

空间复杂度

设定了最高 level，所以空间复杂度只能是 \(\Theta(n)\) 的。

时间复杂度

见 OI Wiki

参考文献

《跳跃表数据结构与算法分析》 纪卓志 George

《跳表》 OI Wiki

推荐阅读

《关于 skip list 的一些扩展想法》

  1. 有的朋友可能会有疑问啊，为什么能够直接取随机数的某一位呢？这不会分布地不够均匀吗？为什么用线性同余而不用统计意义更好的 mt19937 呢？我想用 std::bernoulli_distribution 可以吗？
    本人做了测试，在随机种子 + 1000 次取值的测试下，梅森缠绕和线性同余两种算法通过 & 1 求出来的平均值基本上就是 \(0.5\pm 0.03\)，而且线性同余性能远比梅森缠绕高。然后用 PCG 算法测试了一下，发现 PCG 官方给的 C++ 实现能够做到 \(0.5\pm 0.02\)，性能接近线性同余，但是这玩意考场上得自己实现，所以还是用线性同余吧。
    至于 std::bernoulli_distribution，这东西是取 std::uniform_real_distribution 和设定概率比较做出来的，而 std::uniform_real_distribution 是取随机数之后做一堆浮点运算，效率太低了，而且最后得出来的结果并没有比直接 & 1 强到哪去。↩︎

许可协议

本文采用 GNU 自由文档许可证 许可协议，转载请注明出处。

分享文章