OI-wiki 块状链表（Block List）详解：结构原理、分裂操作与 libstdc++ rope 实战

OI-wiki 块状链表Block List详解结构原理、分裂操作与 libstdc rope 实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读块状链表Block List是一种把「链表」的灵活插入删除能力与「数组」的紧凑存储能力结合起来的数据结构它将长度为 $n$ 的序列切成 $\sqrt{n}$ 个大小约为 $\sqrt{n}$ 的节点每个节点内部用连续数组存储元素节点之间用指针串联。在 OI / ICPC 竞赛中块状链表常用于需要大量随机位置插入、删除与查询的场景其核心优势是所有操作的时间复杂度均为 $O(\sqrt{n})$。本文以 OI-wiki 的 块状链表文档 为主体结合仓库内 示例实现代码 与对应测试数据讲解块状链表的结构定义、分裂机制、定长块大小技巧并介绍 libstdc 中可替代手工实现的rope容器的使用方式最后以 POJ2887「Big String」为例给出完整可运行的模板代码。一、块状链表是什么「块状链表大概就长这样……」OI-wiki 在文档开头给出的示意图即上图docs/ds/images/kuaizhuanglianbiao.png直观展示了其结构块状链表本质上是一个链表只不过链表中的每个节点指向的不是单个元素而是一个数组。原始序列长度为 $n$被划分为约 $\sqrt{n}$ 个节点每个节点内部维护一个大小为 $\sqrt{n}$ 量级的数组连续存储多个元素节点之间通过nxt指针串联形成单向链表。这样的设计同时规避了两类朴素结构的短板纯链表无法随机访问、查找第 $k$ 个元素需要线性遍历纯数组在中间位置插入/删除需要 $O(n)$ 移动元素。块状链表把两者的开销分摊到 $O(\sqrt{n})$是「根号分治」思想的典型数据结构实现。二、节点结构体定义OI-wiki 给出了块状链表节点的最小化结构体定义struct node { node* nxt; int size; char d[(sqn 1) 5]; node() { size 0, nxt NULL, memset(d, 0, sizeof(d)); } void pb(char c) { d[size] c; } };各字段含义如下字段含义nxt指向下一个节点的链表指针size当前节点数组内实际存储的元素个数d[]节点内部存储元素的字符数组容量为 $(2\sqrt{n}5)$其中sqn即 $\sqrt{n}$sqrt(n)的缩写pb是push_back的缩写表示在当前节点数组末尾追加一个元素d[size] c。值得注意的一个细节是数组容量被设计为(sqn 1) 5即约两倍 $\sqrt{n}$ 再加 5 的余量。这不是随手写的而是为后续「分裂split」操作预留的空间——只有当节点元素数超过 $2\sqrt{n}$ 时才触发分裂因此每个节点的数组必须能临时容纳超过一个标准块大小的元素。仓库中的完整实现OI-wiki 仓库在 docs/ds/code/block-list/block-list_1.cpp 中给出了完整实现其中常量定义与节点定义如下#include cctype #include cstring #include iostream using namespace std; constexpr int sqn 1e3; // 块大小常量对应 sqrt(1e6) struct node { // 定义块状链表 node* nxt; int size; char d[(sqn 1) 5]; node() { size 0, nxt NULL; } void pb(char c) { d[size] c; } }* head NULL;这份代码与文档结构体的差异在于题目数据规模为 $10^6$因此将sqn直接取为常量1e3这一点正是下文「定长块大小」技巧的应用构造函数去掉了memset因为插入逻辑总是通过pb写满有效区间且查询只访问size以内的下标无需预先清零。三、分裂split操作一个可用的块状链表至少要支持三种操作分裂、插入、查找。为什么要分裂分裂操作的目的是保证每个节点的大小始终接近 $\sqrt{n}$。如果不做分裂连续向某个节点插入元素会导致其数组无限膨胀最终退化成普通数组——中间插入仍是 $O(n)$ 移动块状链表的意义就消失了。因此约定当一个节点的大小超过 $2\sqrt{n}$ 时立即执行分裂。分裂的具体流程OI-wiki 描述的分裂过程分为四步新建一个节点把被分裂节点的后 $\sqrt{n}$ 个值copy到新节点通过反复size--删除被分裂节点中后 $\sqrt{n}$ 个值把新节点插入到被分裂节点之后更新链表指针。仓库实现中对应的函数是checkvoid check(node* p) { // 判断记得要分裂 if (p-size (sqn 1)) { node* q new node; for (int i sqn; i p-size; i) q-pb(p-d[i]); p-size sqn, q-nxt p-nxt, p-nxt q; } }代码与文字描述一一对应if (p-size (sqn 1))节点大小超过 $2\sqrt{n}$ 即触发for (int i sqn; i p-size; i) q-pb(p-d[i]);把下标从sqn到size-1的后半段元素拷入新节点p-size sqn等价于把被分裂节点的后 $\sqrt{n}$ 个值逐个size--删除这里直接一次性重置更高效q-nxt p-nxt, p-nxt q;新节点接在被分裂节点之后。从源码结构可以推断check通常在每次插入后调用一次即可因为每次插入最多使节点大小增加 1只有越过 $2\sqrt{n}$ 阈值的那一次才会真正触发分裂且分裂后两个节点大小分别约为 $\sqrt{n}$均小于阈值。四、复杂度分析与块大小的取法块状链表的所有操作分裂、插入、查找的复杂度都是 $O(\sqrt{n})$查找第 $k$ 个元素沿链表遍历节点累计各节点size最坏经过约 $\sqrt{n}$ 个节点每个节点内再以 $O(1)$ 下标访问总代价 $O(\sqrt{n})$插入元素先 $O(\sqrt{n})$ 找到目标节点再在数组内移动元素单块内移动至多 $O(\sqrt{n})$必要时执行分裂拷贝 $O(\sqrt{n})$ 个元素分裂单次分裂拷半个块$O(\sqrt{n})$。一个重要的工程技巧把 $\sqrt{n}$ 设为定值随着元素的插入或删除序列长度 $n$ 会变化$\sqrt{n}$ 也会随之变化。难道每次都要重新维护块的大小吗OI-wiki 明确指出其实不然把 $\sqrt{n}$ 设置为一个定值即可。具体做法是根据题目的数据范围上限预先取块大小常量。例如题目给定序列长度上限为 $10^6$那么把块大小设为 $10^3$ 的常量之后全程不再修改。这样既避免了动态调整块的复杂度又能保证最坏情况下每个节点大小始终落在 $O(\sqrt{n_{\max}})$ 量级内操作复杂度依旧为 $O(\sqrt{n_{\max}})$。仓库示例代码正是这样做的constexpr int sqn 1e3; char inits[(int)1e6 5]; // 初始字符串长度上限 1e6STL 组合式写法如果不手写节点也可以用 STL 容器组合出块状链表的形态——用list管理块、每个块内套vectorlistvectorchar orz_list;这种写法的优点是开箱即用list提供 $O(1)$ 的节点插入/删除vector提供块内连续存储缺点是手写实现时仍需自行处理块的拆分合并STL 不会自动维护块大小因此竞赛中常直接手写结构体或使用下文介绍的rope。五、libstdc 中的rope现成的块状链表GNU 的 libstdc 扩展库中提供了一个名为ropeRope large string 的戏称的容器它同样起到块状链表的作用。需要特别说明的是rope内部并不是用真正的块状链表实现的而是采用可持久化平衡树persistent balanced tree实现因此它的时间复杂度不等同于块状链表而是相当于可持久化平衡树的复杂度即 $O(\log n)$。可以把它理解为一个「行为像块状链表、底层是平衡树」的高效大字符串/大数组容器。导入方式#include ext/rope using namespace __gnu_cxx;rope位于 GNU 扩展头文件ext/rope中命名空间为__gnu_cxx。注意双下划线开头的库函数在 OI 中的使用关于能否使用双下划线开头的库函数OI 圈内曾长期存在争议。2021 年 CCF 发布的《关于 NOI 系列活动中编程语言使用限制的补充说明》中提到「允许使用以下划线开头的库函数或宏但具有明确禁止操作的库函数和宏除外」因此rope目前可以在 OI 中正常使用。来源OI-wiki 块状链表文档所引用的官方说明基本操作速查表OI-wiki 总结了rope的常用操作操作作用ropeint a初始化rope与vector等容器很相似可指定元素类型a.push_back(x)在a的末尾添加元素xa.insert(pos, x)在a的第pos个位置插入元素xa.erase(pos, x)从a的第pos个位置开始删除x个元素a.at(x)或a[x]访问a的第x个元素a.length()或a.size()获取a的大小由于底层是平衡树rope的插入、删除、随机访问都能在 $O(\log n)$ 内完成同时天然支持可持久化复制rope对象的代价很小适合处理需要频繁在中间位置插入删除的字符串类问题。六、例题实战POJ2887 Big StringOI-wiki 选用的例题是POJ2887 Big String这是一道非常经典的块状链表模板题题面要求大致如下初始给定一个长度不超过 $10^6$ 的字符串有 $q$ 次操作操作类型有两种I ch pos在第pos个字符之后插入字符chpos可以大于当前长度表示插入到末尾Q pos查询当前字符串中第pos个字符。朴素数组做法在插入时会退化为 $O(n)$ 移动朴素链表做法查询时要 $O(n)$ 遍历而块状链表恰好能把两者都控制在 $O(\sqrt{n})$是该题的理想解法。完整题解代码仓库中的完整实现位于 docs/ds/code/block-list/block-list_1.cpp全文如下#include cctype #include cstring #include iostream using namespace std; constexpr int sqn 1e3; struct node { // 定义块状链表 node* nxt; int size; char d[(sqn 1) 5]; node() { size 0, nxt NULL; } void pb(char c) { d[size] c; } }* head NULL; char inits[(int)1e6 5]; int llen, q; void readch(char ch) { // 读入字符 do cin ch; while (!isalpha(ch)); } void check(node* p) { // 判断记得要分裂 if (p-size (sqn 1)) { node* q new node; for (int i sqn; i p-size; i) q-pb(p-d[i]); p-size sqn, q-nxt p-nxt, p-nxt q; } } void insert(char c, int pos) { // 元素插入借助链表来理解 node* p head; int tot, cnt; if (pos llen) { while (p-nxt ! NULL) p p-nxt; p-pb(c), check(p); return; } for (tot head-size; p ! NULL tot pos; p p-nxt, tot p-size); tot - p-size, cnt pos - tot - 1; for (int i p-size - 1; i cnt; i--) p-d[i 1] p-d[i]; p-d[cnt] c, p-size; check(p); } char query(int pos) { // 查询 node* p; int tot; for (p head, tot head-size; p ! NULL tot pos; p p-nxt, tot p-size); tot - p-size; return p-d[pos - tot - 1]; } int main() { cin.tie(nullptr)-sync_with_stdio(false); cin inits q; llen strlen(inits); node* p new node; head p; for (int i 0; i llen; i) { if (i % sqn 0 i) p-nxt new node, p p-nxt; p-pb(inits[i]); } char a; int k; while (q--) { readch(a); if (a Q) cin k, cout query(k) \n; else readch(a), cin k, insert(a, k); } return 0; }代码逐段解读1初始化建链读入初始字符串后从头节点开始按块填充每填满sqn个字符就新建一个节点for (int i 0; i llen; i) { if (i % sqn 0 i) p-nxt new node, p p-nxt; p-pb(inits[i]); }这段逻辑保证了初始状态下每个节点的size恰好为sqn末尾节点可能不足一块。2插入insert(c, pos)特判pos llen题目允许插入位置超出当前长度表示插到末尾此时直接找到尾节点pb追加并递增总长度否则沿链表累加各节点size定位到第pos个字符应落入的节点p及其块内下标cnt在节点内部从后往前移动元素腾出空位for (int i p-size - 1; i cnt; i--) p-d[i 1] p-d[i];再写入新字符并size最后调用check(p)若节点超限则分裂。3查询query(pos)与插入的定位方式相同累计节点大小直到tot pos然后以 $O(1)$ 下标返回p-d[pos - tot - 1]。4字符读入技巧readch用isalpha过滤掉换行等空白字符避免I c 2中把换行读成待插入字符。测试数据验证仓库在 docs/ds/examples/block-list/block-list_1.in 与 block-list_1.ans 中提供了该题对应的输入输出样例输入block-list_1.inab 7 Q 1 I c 2 I d 4 I e 2 Q 5 I f 1 Q 3期望输出block-list_1.ansa d e可以手动模拟验证初始字符串为abQ 1→ 第 1 个字符aI c 2→ 在第 2 个字符后插c得abcI d 4→pos4大于当前长度 3追加到末尾得abcdI e 2→ 在第 2 个字符后插e得abecdQ 5→ 第 5 个字符dI f 1→ 在第 1 个字符后插f得afbecdQ 3→ 第 3 个字符e。输出a、d、e与样例答案完全一致读者可用该组数据本地验证代码正确性。七、块状链表 vs 相关数据结构把块状链表与它在 OI-wiki 数据结构章节中的近亲做一个横向对比便于按场景选型数据结构随机访问中间插入/删除典型适用场景普通数组$O(1)$$O(n)$只查不改或尾部修改普通链表$O(n)$$O(1)$已知位置只插不改、无随机访问需求块状链表$O(\sqrt{n})$$O(\sqrt{n})$中间插入与查询兼有如 Big String平衡树 /rope$O(\log n)$$O(\log n)$对复杂度要求更高的同类问题在仓库中还可以找到块状链表的更多应用佐证例如 docs/ds/ett.md 的配套代码 docs/ds/code/ett/ett_1.cpp 中提及「上文提到过块状链表实现 ETTEuler Tour Tree在某些情况下可能较简单但对于该题块状链表复杂度有可能无法通过而且实现较繁琐」这说明块状链表也被用作欧拉游览树ETT等进阶数据结构的替代实现方案——当问题规模较小、操作以中间插入删除为主时$O(\sqrt{n})$ 的块状链表往往比平衡树更易编码调试。此外块状链表与 OI-wiki 另一篇文档 块状数组分块 在思想上同源都是根号分治但定位不同块状数组强调「整块打标记 散块暴力」的区间查询块状链表则强调「链表串起多个块」的动态插入删除。两者可以结合理解根号复杂度数据结构的设计思路。总结块状链表是「链表 数组」的复合结构以 $O(\sqrt{n})$ 的均摊复杂度同时支持随机查找与中间插入删除实现难度远低于平衡树是 OI/ICPC 中处理大字符串动态操作问题的实用模板。核心要点可归纳为四点结构每个链表节点内嵌一个容量约 $2\sqrt{n}$ 的数组节点间用nxt串联分裂节点元素数超过 $2\sqrt{n}$ 时把后半段拷到新节点并接在链表中防止退化为数组定块长按题目规模上限把块大小设为常量省去动态维护现成工具libstdc 的rope底层可持久化平衡树提供 $O(\log n)$ 的同类操作可作替代。若需直接复用OI-wiki 仓库中 完整题解代码 与 测试样例 均可作为模板与验证基准。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考