块状链表
块状链表大概就长这样……
不难发现块状链表就是一个链表，每个节点指向一个数组． 我们把原来长度为 n 的数组分为 √𝑛n
个节点，每个节点对应的数组大小为 √𝑛n． 所以我们这么定义结构体，代码见下． 其中 sqn 表示 sqrt(n) 即 √𝑛n，pb 表示 push_back，即在这个 node 中加入一个元素．
实现
---|---
块状链表应该至少支持：分裂、插入、查找． 什么是分裂？分裂就是分裂一个 `node`，变成两个小的 `node`，以保证每个 `node` 的大小都接近 √𝑛n（否则可能退化成普通数组）．当一个 `node` 的大小超过 2 ×√𝑛2×n 时执行分裂操作．
分裂操作怎么做呢？先新建一个节点，再把被分裂的节点的后 √𝑛n 个值 `copy` 到新节点，然后把被分裂的节点的后 √𝑛n 个值删掉（`size--`），最后把新节点插入到被分裂节点的后面即可．
块状链表的所有操作的复杂度都是 √𝑛n 的．
还有一个要说的． 随着元素的插入（或删除），𝑛n 会变，√𝑛n 也会变．这样块的大小就会变化，我们难道还要每次维护块的大小？
其实不然，把 √𝑛n 设置为一个定值即可．比如题目给的范围是 106106，那么 √𝑛n 就设置为大小为 103103 的常量，不用更改它．
---|---
libstdc++ 中的 rope
导入
libstdc++ 中的 rope 也起到块状链表的作用，它采用可持久化平衡树实现，可完成随机访问和插入、删除元素的操作．
由于 rope 并不是真正的用块状链表来实现，所以它的时间复杂度并不等同于块状链表，而是相当于可持久化平衡树的复杂度（即 𝑂(log𝑛)O(logn)）．
可以使用如下方法来引入：
---|---
关于双下划线开头的库函数
OI 中，关于能否使用双下划线开头的库函数曾经一直不确定，2021 年 CCF 发布的 [关于 NOI 系列活动中编程语言使用限制的补充说明](https://www.noi.cn/xw/2021-09-01/735729.shtml) 中提到「允许使用以下划线开头的库函数或宏，但具有明确禁止操作的库函数和宏除外」．故 `rope` 目前可以在 OI 中正常使用．
### 基本操作
操作| 作用
---|---
`rope<int> a`| 初始化 `rope`（与 `vector` 等容器很相似）
`a.push_back(x)`| 在 `a` 的末尾添加元素 `x`
`a.insert(pos, x)`| 在 `a` 的 `pos` 个位置添加元素 `x`
`a.erase(pos, x)`| 在 `a` 的 `pos` 个位置删除 `x` 个元素
`a.at(x)` 或 `a[x]`| 访问 `a` 的第 `x` 个元素
`a.length()` 或 `a.size()`| 获取 `a` 的大小
## 例题
[POJ2887 Big String](http://poj.org/problem?id=2887)
题解： 很简单的模板题．代码如下：
---|---
本页面最近更新： 2026/1/27 11:38:23，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, ChungZH, HeRaNO, konnyakuxzy, ksyx, Tiphereth-A, Chrogeek, Enter-tainer, iamtwz, kenlig, littlefrog, littlefrogfromthenorth, megakite, sgt57, shuzhouliu, StudyingFather, Xeonacid 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用