块状链表详解

众所周知，数组可以以 \(O(1)\) 的复杂度查询、修改元素，但删除和插入元素的复杂度是 \(O(n)\) 的；链表恰好相反，插入、删除元素的复杂度为 \(O(1)\)，但查询为 \(O(n)\)。

有没有能以较优复杂度完成插入、删除、查询、修改操作的线性数据结构？

本篇介绍的块状链表就可以。
顾名思义，块状链表运用分块的思想，将数组与链表结合起来。这里引用一张经典的图来展示它大概的样子：

可以看出块状链表就是以数组为节点（块）的链表。
例一

我们借P4008 [NOI2003] 文本编辑器这道题来理解块状链表的各个操作。

维护一个字符串，支持在指定位置插入字符串、删除字符串、查询指定长度的连续字串。

内存分配

与正常的链表一样，块状链表中会出现很多新建、删除节点的操作，必须让被删除节点的位置能被新节点再次占用，否则会产生很多空节点，从而使内存巨大。为此我们使用作为内存池的栈 \(pool[]\)。

1. void init()
2. {
3.     for(int i=1;i<=mxnum;i++)//初始化内存池
4.         pool[i]=i;
5.     sz[0]=0;
6.     nxt[0]=-1;//标记链表的结尾
7. }
9. int new_block()
10. {
11.     return pool[++num];//取出栈顶空节点
12. }
14. void del_block(int x)
15. {
16.     pool[num--]=x;//将被删除的节点压入栈顶
17. }

复制代码

例三

P2596 [ZJOI2006] 书架

给定一个 \(1\)~\(n\) 的排列，操作为将某个数放到最前面、放到最后面或向前、后移动一步，询问 \(s\) 位置的数或数 \(s\) 的位置。

这三种操作都可以视为从排列中删除一个数，再插入一个数。
这道题中比较麻烦的一点是，移动数的操作给定的都是数的值，因此可以给每一个块开一个桶 \(book[]\) 以记录其中是否包含某个数，进行移动操作之前先查询位置。
[code]#include using namespace std;const int N=405;int n,m,k;int a[N][N],sz[N],pool[N],nxt[N],book[N][80005];void init(){    for(int i=1;i