块状链表

块状链表的意义

有时候我们需要设计这样一种数据结构：它能快速在要求位置插入或者删除一段数据。

先考虑两种简单的数据结构：数组和链表

数组能够在O(1)的时间内找到所要执行操作的位置，但无论是插入或删除都要移动之后的所有数据，复杂度是O(n)的。

链表能够在O(1)的时间内插入和删除一段数据，但是在寻找操作位置时，却要遍历整个链表，复杂度同样时O(n)的。

这两种数据结构各有优缺点，我们尝试将两种数据结构融合成一个全新的数据结构：块状链表。

为了体现块状链表的优越性，我们再举个例子：

先搬道题目出来:

编程实现一个文本编辑器的功能，操作有:移动光标，删除光标后XX个字符，在光标后添加一段文本，输出光标后XX个字符。

首先，我们来讨论一下暴力写法。

No.1:数组:

用数组实现这些操作，我们看下总时间复杂度分析:

移动光标:O(1*times(<=50000))

删除光标后XX个字符:O(总字符数(<=2MB)*times(<=4000))

在光标后添加一段文本:O(总字符数*times(<=4000))

输出光标后XX个字符:O(P)

//备注:P<=3MB, 输出光标后XX个字符在所有算法中复杂度相同,接下来将会略去

在询问次数较多，并且添删字符较多是必定会超时

No.2:链表:

移动光标:O(n*times(<=50000))

删除光标后XX个字符:O(总字符数)

在光标后添加一段文本:O(总字符数)

现在，轮到块状链表登场了:

移动光标:O(sqrt(n)*times(<=50000))

删除光标后XX个字符:O(sqrt(总字符数))

在光标后添加一段文本:O(sqrt(总字符数))

{均摊平衡树SplayTree可以做到所有操作均摊O(Log(总字符数))}

块状链表的具体介绍

块状链表是这样的：从总体上来看，维护一个链表，链表中的每个单元中包含一段数组，以及这个数组中的数据个数。

每个链表中的数据连起来就是整个数据。

设链表长度为a，每个单元中的数组长度是b。

无论是插入或删除，在寻址时要遍历整个链表，复杂度是O(a)；

对于插入操作，直接在链表中加入一个新单元，复杂度是O(1)；

对于删除操作，会涉及多个连续的单元，如果一个单元中的所有数据均要删除，直接删除这个单元，复杂度是O(1)，如果只删除部分数据，则要移动数组中的数据，复杂度是O(b)。

总的复杂度是O(a+b)。

因为ab=n，取a=b=√n，则总的复杂度是O(√n)。

问题是如何维护a和b大致等于√n？

必须维持块状链表中每块的大小在区间[sqrt(n)/2,sqrt(n)*2]中，否则，块状链表会退化。维护可以通过块的合并与分裂完成，合并复杂度，同样是O(sqrt(n))

这样，维护操作并不会使总复杂度增加。

最终得到一个复杂度是O(√n)的数据结构。

块状链表的实现

以noi2003的editor题目为例

'''C++版''' {这是保存光标位置的做法}

/******************************
            块状链表
    For NOI2003 :     Editor
    Author:        DarkRaven
 *****************************/
#include<iostream>
#include<cmath>
#define MAX 2900
struct block{//Type of block
    int nos;//Number of elements in this block
    char em[MAX];//elements 
    block *be,*su;//previous&successor
}*first;
struct cursor{//Type of cursor
    int n;//The postion of cursor(in one block)
    block *ll;//The block the cursor in
}cur;
int tot,n;//tot:the total number of elements,n:the number of operations
inline void clean(block *op){//Clean a new block
    op->nos=0;
    memset(op->em,0,sizeof op->em);
    op->be=NULL;
    op->su=NULL;
}
inline void Spilt(block *a,int newsize){//Break a block into two blocks,one's size equal to 'newsize',and another's equal to 'a->nos-newsize'
    if(!newsize)return;
    int tmp=a->nos;
    a->nos=newsize;
    block *tps=a->su;
    a->su=new(block);
    clean(a->su);
    a->su->be=a;
    if(tps){
        a->su->su=tps;
        a->su->su->be=a->su;
    }
    a->su->nos=tmp-newsize;
    block *tt=a->su;
    for(int i=newsize+1;i<=tmp;i++)tt->em[i-newsize]=a->em[i];
}
inline void Merge(block *a){//Merge a & a->su
    if(a->su==NULL)return ;
 int tmp=a->nos;
    for(int i=1;i<=a->su->nos;i++)a->em[a->nos+i]=a->su->em[i];
    a->nos+=a->su->nos;
    block *oo=a->su;
 if(cur.ll==oo){
  cur.ll=cur.ll->be;
  cur.n+=tmp;
 }
    a->su=a->su->su;
    delete(oo);
    if(a->su)a->su->be=a;
}
inline void Balance(){//Make these blocks' size balance
    block *k=first;
    int kk=(int)sqrt(tot);
    for(;k!=NULL;){
        for(;k->nos < kk/2 || k->nos > 2*kk;){
            if(k->nos<kk/2){//the block is too small?
                if(k->su)Merge(k);
                else break;
            }
            else if(k->nos>kk*2){//the block is too big?
    Spilt(k,(k->nos)>>1);
    if((cur.ll==k)&&(cur.n>k->nos)){
                    cur.ll=k->su;
                    cur.n-=k->nos;
                }
    k=k->su;
    }
        }
  k=k->su;
    }
}
inline void Insert(block *lk,int x,int k){//Insert text behind the cursor
     block *oo=new(block);
    clean(oo);
    block *gg=oo;
    int rr=k;
    tot+=rr;
    int bt=(int)sqrt(tot);
    for(int i=0;i<rr;i++){
     char gg;
  scanf("%c",&gg);
  for(;(gg>126)||(gg<32);scanf("%c",&gg));
  oo->em[++oo->nos]=gg;
  if((oo->nos>=bt)&&(i<rr-1)){
   oo->su=new(block);
   clean(oo->su);
   oo->su->be=oo;
   oo=oo->su;
  }
 }
 if(x){
  Spilt(lk,x);
 }
 else {
  if(!cur.ll->be){
   block *jj;
   jj=first;
   first=new(block);
   clean(first);
   first->su=jj;
   jj->be=first;
  }
  cur.ll=cur.ll->be;
  cur.n=cur.ll->nos;
  lk=lk->be;
 }
 block *tmp=lk->su;
 lk->su=gg;
 oo->su=tmp;
 if(oo->su)oo->su->be=oo;
 lk->su->be=lk;
 cur.ll=lk->su;
 cur.n=0;
 Balance();
}
inline void Remove(block *lk,int x,int num){ //Delete 'num' elements behind the cursor
 if(x){
  Spilt(lk,x);
  lk=lk->su;
 }
 else {
  if(!cur.ll->be){
   block *jj;
   jj=first;
   first=new(block);
   clean(first);
   first->su=jj;
   jj->be=first;
  }
  cur.ll=cur.ll->be;
  cur.n=cur.ll->nos;
 }
 tot-=num;
 int ttt=num;
 block *tmp;
 block *ii;
 for(tmp=lk;tmp&&((num-tmp->nos)>=0);tmp=ii){
  ii=tmp->su;
  num-=tmp->nos;
  delete(tmp);
 }
 if(num&&tmp){
  Spilt(tmp,num);
  cur.ll->su=tmp->su;
  cur.ll->su->be=cur.ll;
  if(cur.ll->be)cur.ll->be->su=cur.ll;
 }
 else {
  cur.ll->su=tmp;
  if(cur.ll->be)cur.ll->be->su=cur.ll;
  if(cur.ll->su)cur.ll->su->be=cur.ll;
 }
 Balance();
}  
inline void Print(block *lk,int x,int num){//print 'num' elements behind the cursor
 block *cp=lk;
 for(;num-(cp->nos-x)>0;cp=cp->su){
  for(int i=x+1;i<=cp->nos;i++)printf("%c",cp->em[i]);
  num-=(cp->nos-x);
  x=0;
 }
 for(int i=1;i<=num;i++)printf("%c",cp->em[i+x]);
 printf("\n");
}
inline void prev(){//cursor move forward
 cur.n--;
 if(cur.n<0){
  cur.ll=cur.ll->be;
  cur.n=cur.ll->nos-1;
 }
}
inline void next(){//cursor move backward
 cur.n++;
 if((cur.n>=cur.ll->nos)&&(cur.ll->su)){
  cur.ll=cur.ll->su;
  cur.n-=cur.ll->be->nos;
 }
}
inline void move(int k){//move the cursor to the postion 'k'
 cur.ll=first;
 for(;(cur.ll)&&(k-cur.ll->nos>0);cur.ll=cur.ll->su)
 k-=cur.ll->nos;
 cur.n=k;
}
int main(){
 freopen("editor.in","r",stdin);
 freopen("editor.out","w",stdout);
 first=new(block);
 clean(first);
 char str[100];
 cur.ll=first;
 cur.n=0;
 scanf("%d\n", &n);
 int k;
 for (int i=0;i<n;i++) {
  scanf("%s", str);
  switch (str[0]) {//deal with operations
      case 'M' : scanf("%d", &k); move(k); break;
            case 'I' : scanf("%d", &k); Insert(cur.ll,cur.n,k); break;
            case 'D' : scanf("%d", &k); Remove(cur.ll,cur.n,k); break;
            case 'G' : scanf("%d", &k); Print(cur.ll,cur.n,k);; break;
            case 'P' : prev(); break;
            case 'N' : next(); break;
        }
    }
 
    fclose(stdin);
    fclose(stdout);
}

Pascal版

{维护了一个Jason域用于二分查找光标位置（Jason[i，1]为1..i块的长度和，Jason[i,2]为第二块的位置）} {其实不用每次都重新算一遍，不过我懒得写了，估计也快不了多少} {这里要是写“块状跳表”“块状平衡树”的话有点秃}

{1.发现Maxm开大了的话会慢很多 不知道为什么} {2.Union操作，我怀疑Jason那个块状链表也是不能保证 块的长度都是合法的} {3.一定要注意等号 就是这个等号 我昨天Debug了一夜} {4.Jason770如是说，想好了再编程} {5.AnsiString貌似是链表没法Watch，AnsiString的效率要比String和WideString高很多，也省空间} {6.个人怀疑维护Jason会变慢，因为我偷懒，没维护Prev} {7.个人怀疑我的输出要比Jason770天牛慢} {8:Insert的最后一句一定要Union（x），Union（Last）的话会死得很惨} {9.该程序还有改进余地} {============================膜拜Jason770天牛Orz=================================} {by cjf00000} {============================膜拜cjf天牛和AlNo3天牛===============================} {Morenan弱菜}

program editor;
 
const maxm = 10000; Cjf= 3000;
      fin = 'editor.in'; fout = 'editor.out';
type bartype=record
      next:longint;
      data:ansistring;
end;
var a:array[0..maxm]of bartype;
      Jason:array[0..maxm,1..2]of longint;
n,k,Cursor,Open,TotBar,Head:longint;
str,temp:ansistring;
ch:char;
 
Procedure ReadSpace;                                      //读入多余字符
begin
    read(ch);
    while ch<>' ' do read(ch);
end;
 
Function Search(Cursor:longint):longint;                 //返回Cursor所在的是第几个块
var l,r,mid:longint;
begin
    l:=1;r:=totbar;
    while l+1<r do begin
      mid:=(l+r) div 2;
      if Jason[mid,1]<cursor then l:=mid
      else r:=mid;
    end;
    if l+1=r then if Jason[l,1]>=cursor then exit(l) else exit(r);
    exit(l);
end;
 
Procedure ReadForInsert;                                //读入字符串
begin
    str:='';
    while k>0 do begin
      readln(temp);
      str:=str+temp;
      dec(k,length(temp));
    end;
    k:=length(str);
end;
 
Procedure Ccopy;                                        //Ccopy=Cut
begin
    if length(str)>Cjf then begin
      A[open].data:=Copy(str,1,Cjf);
      Delete(str,1,cjf);
    end
    else begin
      A[open].data:=Copy(str,1,length(str));
      str:='';
    end;
end;
 
Procedure CalcNewJason;
Var Now,count:Longint;
Begin
    Fillchar(Jason,Sizeof(Jason),0);
    Now:=Head;Count:=0;
    While Now<>0 do begin
      Inc(Count);
      Jason[Count,1]:=Jason[Count-1,1]+Length(A[Now].Data);
      Jason[Count,2]:=Now;
      Now:=A[Now].Next;
    End;
    Totbar:=Count;
End;
 
Procedure Union(Start:longint);
Var Now,Sum,Count:Longint;
Begin
    Now:=A[Start].Next;Count:=0;Sum:=Length(A[Start].Data);
    While (Sum+Length(A[Now].Data)<=Cjf)and(Now<>0) do begin         //合并字串
      Sum:=Sum+Length(A[Now].Data);
      A[Start].data:=A[Start].data+A[Now].data;
      Now:=A[Now].Next;
      Inc(Count);
    end;
    A[Start].Next:=Now;
    CalcNewJason;
end;
 
Procedure InsertStr;
Var ssfzzzc,x,y,count,last,ra224:longint;
Begin
    ssfzzzc:=Search(Cursor+1);
    x:=Jason[ssfzzzc,2];
    y:=Cursor+1-Jason[ssfzzzc-1,1];
    If x=0 then begin
      x:=1;
      Inc(Open);Inc(Totbar);
      Head:=Open;
    end;
 
    ReadForInsert;
    count:=length(str) div Cjf+1;
    if length(str) mod Cjf>0 then inc(count);last:=x;   //预处理
    inc(Totbar,count);
 
    Inc(Open);inc(count);Ra224:=Open;                   //将Y及后面的字符新开一段
    A[Open].data:=Copy(A[x].data,y,length(a[x].data)-y+1);
    A[Open].Next:=A[x].Next;
    Delete(A[x].data,y,length(a[x].data)-y+1);
 
    count:=0; Last:=x;
    while length(str)>0 do begin                        //存储刚插入的字符串
      inc(count);Inc(Open);
      CCopy;
      A[Last].next:=Open;
      Last:=Open;
    end;
 
    A[Last].next:=Ra224;
    Union(X);                 
End;
 
Procedure DeleteStr;
Var count,ssfzzzc,sum,now,x,y:longint;
Begin
    ssfzzzc:=Search(Cursor+1);                         //ssfzzzc表示光标在第几块
    x:=Jason[ssfzzzc,2];
    y:=Cursor+1-Jason[ssfzzzc-1,1];
 
    If k<=Length(A[X].Data)-y+1 then begin
      Delete(A[x].Data,y,k);
    end
    else begin
      Sum:=Length(A[x].Data)-y+1;Delete(A[x].Data,y,Length(A[x].Data)-y+1);
      Now:=A[x].Next;Count:=0;
      While Sum+Length(A[Now].Data)<k do begin       //删中间的块
        Inc(count);
        Inc(Sum,Length(A[Now].Data));
        Now:=A[Now].Next;
      end;
      Delete(A[Now].Data,1,k-sum);
      A[x].Next:=Now;
      Totbar:=Totbar-count;
    end;
    Union(x);
End;
 
Procedure Get;
Var SsfzZzc,x,y,count:Longint;
Begin
    ssfzzzc:=Search(Cursor+1);                         //ssfzzzc表示光标在第几块
    x:=Jason[ssfzzzc,2];
    y:=Cursor+1-Jason[ssfzzzc-1,1];
 
    count:=0;
    While (count<k) do begin
      inc(count);
      write(A[x].data[y]);
      if y<length(A[x].data) then inc(y) else begin
        x:=A[x].Next;
        y:=1;
      end;
    end;
    writeln;
End;
 
Procedure Zhouye;
Var k:longint;
begin
    k:=head;
    while A[k].next<> 0 do begin
      writeln(length(a[k].data));
      k:=a[k].next;
    end;
end;
 
Procedure main;
var i:longint;
begin
    assign(input,fin);reset(input);
    assign(output,fout);rewrite(output);
    readln(n);
    Open:=0;TotBar:=0;Cursor:=0;Head:=0;
    for i:=1 to n do begin
      read(ch);
      case ch of
        'N':begin
          readln;Inc(Cursor);
        end;
        'P':begin
          readln;Dec(Cursor);
        end;
        'M':begin
          ReadSpace;readln(k);Cursor:=k;
        end;
        'I':begin
          ReadSpace;readln(k);InsertStr;
        end;
        'D':begin
          ReadSpace;readln(k);DeleteStr;
        end;
        'G':begin
          ReadSpace;readln(k);Get;
        end;
      end;
    end;
    close(input);close(output);
end;
 
begin
    Main;
end.

参考资料

北极天南星 数组+链表=块状链表 [1]

lightxianjian 块状链表 [2]

cjf00000 关于Noi2003 Editor（块状链表） [3]