块状链表

块状链表大概就长这样……

不难发现块状链表就是一个链表，每个节点指向一个数组。 我们把原来长度为 n 的数组分为 个节点，每个节点对应的数组大小为 。 所以我们这么定义结构体，代码见下。 其中 sqn 表示 sqrt(n) 即 ，pb 表示 push_back，即在这个 node 中加入一个元素。

块状链表应该至少支持：分裂、插入、查找。 什么是分裂？分裂就是分裂一个 node，变成两个小的 node，以保证每个 node 的大小都接近 （否则可能退化成普通数组）。当一个 node 的大小超过 时执行分裂操作。

分裂操作怎么做呢？先新建一个节点，再把被分裂的节点的后 个值 copy 到新节点，然后把被分裂的节点的后 个值删掉（size--），最后把新节点插入到被分裂节点的后面即可。

块状链表的所有操作的复杂度都是 的。

还有一个要说的。 随着元素的插入（或删除）， 会变， 也会变。这样块的大小就会变化，我们难道还要每次维护块的大小？

其实不然，把 设置为一个定值即可。比如题目给的范围是 ，那么 就设置为大小为 的常量，不用更改它。

STL 中的 rope

导入

STL 中的 rope 也起到块状链表的作用，它采用可持久化平衡树实现，可完成随机访问和插入、删除元素的操作。

由于 rope 并不是真正的用块状链表来实现，所以它的时间复杂度并不等同于块状链表，而是相当于可持久化平衡树的复杂度（即 ）。

可以使用如下方法来引入：

基本操作

操作	作用
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

题解： 很简单的模板题。代码如下：