块状链表的相关概念

块状链表： 用链表的形式将所有块连接在一起，就称为 块状链表

块状链表的作用： 我们知道分块能将一整段序列分成若干块，然后通过一种优美的暴力来处理每一块的信息。如果我们要在某一个位置加入一段新的序列，而普通的分块是用数组存储所有块的，显然并不支持这类操作，此时我们就可以用链表的形式来存储所有块，而链表就能快速的实现添加一块的操作，这其实就是块状链表，块状链表能非常容易的实现将加入、删除甚至翻转某一段区间的操作。块状链表一般在用平衡树实现代码非常复杂时使用。

块状链表的原理：

对于块状链表，区别于普通分块，块状链表种每一块的长度都是不定的。

插入操作：

如果我们想在某个位置插入一段，我们可以先将这个位置所在的块从这个位置断开成两小段，再在这两小段之间重新连上。这一步的实际操作其实就是将当前块中断开的位置后面的一段复制到一个新的块中，再将这个新的块插入到当前块的后面。

接下来我们只需要将要插入的元素插入到断开的这两小段之间，因此可以将我们要插入的序列建成一个块状链表，然后将这个新的块状链表插入到两小段之间即可。

删除操作：

如果我们想要删除某一段，删除的部分可以分成三个部分，第一个部分就是前面某一块的后缀，第二部分是中间被完全包含的所有块，第三部分是后面某一块的前缀。我们只需要依次将这三个部分都删掉即可。

合并操作：

在执行插入操作时我们会将某一块断开，如果断开的位置比较特殊，可能导致断开的前一段中节点很多，后一段中节点却非常少，进行大量插入操作之后可能到这块状链表中存在很多节点数非常少的块，并且此时块状链表中块的数量也会远远大于 $\sqrt{n}$，这会严重影响我们的运行效率，因此我们需要定期去合并块状链表。

合并操作就是遍历整个链表，对于每个块，判断一下当前块能否和下一个块合并，如果当前块的长度加上下一个块的长度不超过每个块的长度上限，就将下一个节点合并到当前节点中。

通过合并操作之后，我们会发现任意两个相邻的块的长度之和都 $\geq \sqrt{n}$，因此每个块的平均长度就会 $\geq \frac{\sqrt{n}}{2}$，那么块的数量就会 $\leq 2\sqrt{n}$，这样就能保证块的数量不会太多，不至于影响我们的运行效率。

内存回收机制：

由于块状链表擅长的操作就是快速插入和删除一段序列，因此该数据结构处理的问题一般都是有大量插入和删除操作的问题，因此每个下标可能会用到多次，所以块状链表也需要一个栈来回收没用的下标，方便在下一次继续使用。