块状链表：实现高效插入、删除、查询与修改的线性数据结构

众所周知，数组可以以 \(O(1)\) 的复杂度查询、修改元素，但删除和插入元素的复杂度是 \(O(n)\) 的；链表恰好相反，插入、删除元素的复杂度为 \(O(1)\)，但查询为 \(O(n)\)。 > > > 有没有能以较优复杂度完成插入、删除、查询、修改操作的线性数据结构？ > 本篇介绍的块状链表就可以。 顾名思义，块状链表运用分块的思想，将数组与链表结合起来。这里引用一张经典的图来展示它大概的样子：  可以看出块状链表就是以数组为节点（块）的链表。 ## 例一 我们借[P4008 \[NOI2003\] 文本编辑器](https://www.luogu.com.cn/problem/P4008)这道题来理解块状链表的各个操作。 > > > 维护一个字符串，支持在指定位置插入字符串、删除字符串、查询指定长度的连续字串。 > ### 内存分配 与正常的链表一样，块状链表中会出现很多新建、删除节点的操作，必须让被删除节点的位置能被新节点再次占用，否则会产生很多空节点，从而使内存巨大。为此我们使用作为内存池的栈 \(pool[]\)。 ```csharp void init() { for(int i=1;i<=mxnum;i++)//初始化内存池 pool[i]=i; sz[0]=0; nxt[0]=-1;//标记链表的结尾 } int new_block() { return pool[++num];//取出栈顶空节点 } void del_block(int x) { pool[num--]=x;//将被删除的节点压入栈顶 } ``` ### 合并 为了保证复杂度，需要同时限制块的总数与最大块长。一个很好的方法是，对于相邻的块，如果他们的长度和不超过最大块长，就将他们合并。  ```csharp void merge(int x,int y) { cpy(dt[x]+sz[x],dt[y],sz[y]);//手写的复制函数，与memcpy功能相同 nxt[x]=nxt[y]; sz[x]+=sz[y]; del_block(y);//合并后，多出来的块要删掉 } void maintain()//遍历整个链表，合并所有可以合并的相邻块 { for(int x=0,y=nxt[0];x!=-1;x=nxt[x],y=nxt[x]) while(y!=-1 && sz[x]+sz[y]<=mxsize) { merge(x,y); y=nxt[x]; } } ``` ### 分裂 在插入或删除元素时，需要将待操作位置单独分成块，再进行类似链表的插入、删除操作。  ```csharp void update(int x,int y,int len,char *s) { nxt[y]=nxt[x]; nxt[x]=y; sz[y]=len; cpy(dt[y],s,len); } void split(int x,int pos) { if(x==-1 || pos==sz[x]) return; int y=new_block(); update(x,y,sz[x]-pos,dt[x]+pos);//新建块 sz[x]=pos;//记得更新原块长 } ``` ### 具体操作 - 插入：将插入位置的块分裂，把待插入字符串分成长度不超过 \(mxsize\) 的块，依次插入。 - 删除：将要删除的左右端点的块分裂，删去中间所有块。 - 查询：将会被查到的所有块复制到答案字符串上。  ```csharp int get_pos(int &pos)//将输入的位置转换成块上的位置 { int x=0; while(x!=-1 && pos>sz[x]) { pos-=sz[x]; x=nxt[x]; } return x; } void insert(int pos,int len) { int x=get_pos(pos),y,sum=0; split(x,pos); while(sum+mxsize<=len) { y=new_block(); update(x,y,mxsize,s+sum); sum+=mxsize; x=y; } if(len>sum)//如果切完后还有剩余，尾部自成一块 { y=new_block(); update(x,y,len-sum,s+sum); } maintain();//插入的左、右端点处可能可以合并，后面删除操作的maintain()同理 } void erase(int pos,int len) { int x=get_pos(pos),y; split(x,pos); y=nxt[x]; while(y!=-1 && len>0) { if(sz[y]>len) split(y,len); len-=sz[y]; del_block(y); y=nxt[y]; } nxt[x]=y;//记得指向下一块 maintain(); } void query(int pos,int len) { int x=get_pos(pos),sum=sz[x]-pos; if(lensum) cpy(s+sum,dt[x],len-sum); s[len]=0;//标记串的结尾 printf("%s\n",s); } ``` 容易得出，当最大块长为 \(\sqrt n\) 时，插入、删除和查询的复杂度均为 \(O(\sqrt n+len)\)。 ### 总体代码 ```csharp #include using namespace std; const int N=1024*1024+5; const int mxsize=3000,mxnum=N*2/mxsize+5;//要开到N的两倍 int q; int num,nxt[mxnum],sz[mxnum],pool[mxnum]; char dt[mxnum][mxsize],s[N]; void cpy(char *a,char *b,int len) { for(int i=0;i126) s[i]=getchar(); } } //省略 int main( void ) { scanf("%d",&q); init(); int pos=0; while(q--) { char rd[10]; scanf("%s",rd); if(rd[0]=='M') scanf("%d",&pos); else if(rd[0]=='I') { int len; scanf("%d",&len); gets(len); insert(pos,len); } else if(rd[0]=='D') { int len; scanf("%d",&len); erase(pos,len); } else if(rd[0]=='G') { int len; scanf("%d",&len); query(pos,len); } else if(rd[0]=='P') pos--; else if(rd[0]=='N') pos++; } return 0; } ``` ## 例二 [P3391 【模板】文艺平衡树](https://www.luogu.com.cn/problem/P3391) > > > 给定一个长度为 \(n\) 的序列 \(a\)，初始 \(a\_i=i\)，执行多次区间翻转操作，求操作后序列。 > 将需要翻转的区间中的所有块顺序翻转，并给每一块打上翻转标记，在合并、分裂时检查标记。 ```csharp void rev(int x) { if(tag[x]) reverse(a[x],a[x]+sz[x]); tag[x]=0;//翻转后取消标记 } void rotate(int pos,int len) { int x=get_pos(pos); split(x,pos); int y=nxt[x]; top=0; while(len>0) { if(sz[y]>len) split(y,len); len-=sz[y]; sta[++top]=y; tag[y]^=1;//注意这里不能直接=1 y=nxt[y]; } sta[++top]=x; sta[0]=y; for(;top>=1;top--) nxt[sta[top]]=sta[top-1];//反着连接块 maintain(); } ``` ## 例三 [P2596 \[ZJOI2006\] 书架](https://www.luogu.com.cn/problem/P2596) > > > 给定一个 \(1\)~\(n\) 的排列，操作为将某个数放到最前面、放到最后面或向前、后移动一步，询问 \(s\) 位置的数或数 \(s\) 的位置。 > 这三种操作都可以视为从排列中删除一个数，再插入一个数。 这道题中比较麻烦的一点是，移动数的操作给定的都是数的值，因此可以给每一个块开一个桶 \(book[]\) 以记录其中是否包含某个数，进行移动操作之前先查询位置。 ```csharp #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<=N-5;i++) pool[i]=i; nxt[0]=-1; } int new_block() { return pool[++k]; } void del_block(int x) { for(int i=0;isz[x]) { pos-=sz[x]; x=nxt[x]; } return x; } void insert(int pos,int num) { int x=get_pos(pos); split(x,pos); int y=new_block(); update(x,y,1,&num); maintain(); } void remove(int pos) { int x=get_pos(pos); split(x,pos); int y=nxt[x]; split(y,1); nxt[x]=nxt[y]; del_block(y); maintain(); } int query(int pos) { int x=get_pos(pos); return a[x][pos-1]; } int askk(int id) { int x=0,num=0; while(!book[x][id]) { num+=sz[x]; x=nxt[x]; }//跳到包含id的块 for(int i=0;i