块状链表详解
众所周知，数组可以以 \(O(1)\) 的复杂度查询、修改元素，但删除和插入元素的复杂度是 \(O(n)\) 的；链表恰好相反，插入、删除元素的复杂度为 \(O(1)\)，但查询为 \(O(n)\)。有没有能以较优复杂度完成插入、删除、查询、修改操作的线性数据结构？
本篇介绍的块状链表就可以。
顾名思义，块状链表运用分块的思想，将数组与链表结合起来。这里引用一张经典的图来展示它大概的样子：
可以看出块状链表就是以数组为节点（块）的链表。
例一
我们借P4008 文本编辑器这道题来理解块状链表的各个操作。
维护一个字符串，支持在指定位置插入字符串、删除字符串、查询指定长度的连续字串。
内存分配
与正常的链表一样，块状链表中会出现很多新建、删除节点的操作，必须让被删除节点的位置能被新节点再次占用，否则会产生很多空节点，从而使内存巨大。为此我们使用作为内存池的栈 \(pool[]\)。
void init()
{
for(int i=1;i<=mxnum;i++)//初始化内存池
pool=i;
sz=0;
nxt=-1;//标记链表的结尾
}
int new_block()
{
return pool[++num];//取出栈顶空节点
}
void del_block(int x)
{
pool=x;//将被删除的节点压入栈顶
}例三
P2596 书架
给定一个 \(1\)~\(n\) 的排列，操作为将某个数放到最前面、放到最后面或向前、后移动一步，询问 \(s\) 位置的数或数 \(s\) 的位置。
这三种操作都可以视为从排列中删除一个数，再插入一个数。
这道题中比较麻烦的一点是，移动数的操作给定的都是数的值，因此可以给每一个块开一个桶 \(book[]\) 以记录其中是否包含某个数，进行移动操作之前先查询位置。
#include using namespace std;const int N=405;int n,m,k;int a,sz,pool,nxt,book;void init(){ for(int i=1;i
页:
[1]