块状链表学习笔记

· · 个人记录

0.前言

先摆上效果qwq

大家都知道，数组定位复杂度为O(1)，插入删除的复杂度为O(n)。

不过，链表倒相反：定位复杂度为O(n)，插入删除的复杂度为O(1)。

虽然这两种数据结构用起来都十分方便，但问题来了：如果有既要插入删除，又要快速定位元素的问题时，有没有一种数据结构能够同时快速支持这两个操作呢？

它就是——块状链表（数组）！

1.块状链表是啥？

块状链表的主要思想是分块 （一种优雅的暴力），它把数组和链表的优点相结合，平衡了复杂度，使每个节点对应的数组长度为\sqrt{n}级别。所以，在定位、查询或插入、删除时复杂度保持在O(\sqrt{n})。如果操作数与元素数量同阶，复杂度为O(n\sqrt{n})。（序列之王Splay好！）

2.基本操作

前置芝士：

memcpy指的是C和C++使用的内存拷贝函数，函数原型为void *memcpy(void *destin, void *source, unsigned n)；函数的功能是从源内存地址的起始位置开始拷贝若干个字节到目标内存地址中，即从源source中拷贝n个字节到目标destin中。

destin——指向用于存储复制内容的目标数组，类型强制转换为 void* 指针。

source——指向要复制的数据源，类型强制转换为 void* 指针。

n——要被复制的字节数。

该函数返回一个指向目标存储区destin的指针。

以上摘自百度百科

分配及回收节点

int p[MAXN],tot;
int new_node(){
    return p[tot--];
}//分配
void cycle(int x){
    p[++tot] = x;
}//回收
void start(){
    for(int i=1;i<MAXN;i++){
        p[++tot]=MAXN-i;
    }
}//初始状态

节点

struct node{
    int szl,next;
    int s[MAXS*4];//此处数据类型可改变
};

查询

int search(int &p) {
    int x = 0;
    while(x!=-1&&a[x].sz<p){
    p-=a[x].szl,x=a[x].next;
    }
    return x;
}

暴力插入

流程如下：

（蒟蒻图画得不好不要怪我啊QAQ）

具体程序：

void ins(int x,int y,int l,char *s){
    if(x!=-1){  //特判x指向链表末尾
        a[y].szl=l;
        a[y].next=a[x].next;
        memcpy(a[y].s,s,l);
    }
    a[x].next=y;
}
//此示例演示在编号为x的节点后插入一个编号为y,长度为l,对应数组为s的节点

合并节点

void mesh(int x,int y){
    memcpy(a[x].s+a[x].szl,a[y].s,a[y].szl);
    a[x].szl+=a[y].szl;
    a[x].next=a[y].next;
    del(y);
}//把y接在x的后面,然后把y删除

分裂节点

void split(int x,int w){
    if(x==-1||w==a[x].szl) return;
    int t=new_node();//分裂后多出一个节点
    insert(x,t,a[x].szl-w,a[x].szl+w);
    a[x].szl=w;
}

3.具体实例

引例1

P4195 【模板】扩展BSGS

先从模版开始打！（块状链表模版怎么都是紫的啊qwq，钻研了好久）

前置芝士：

欧拉定理（Euler Theorem）：若a、n分别为正整数，并且a、n互质，则有：a^{\varphi(n)}\equiv1\;(mod\;p)

BSGS：给定a，p，b，其中(a,p)=1，求最小整数解x，满足a^x{\equiv}\;b\;(mod\;p)，p是质数

分析

根据定理可得，a^x最多只有\varphi(p)个，所以考虑x{\in}\lbrack0,\varphi(p)\rbrack的情况。

然后令x=im-k，开始分块，得a^{im-k}{\equiv}\;b\;(mod\;p)

化一下a^{im}{\equiv}\;b\times{a^k}\;(mod\;p)

令m=\sqrt{n}，暴力枚举k{\in}\lbrack0,m-1\rbrack，把b\times{a^k}插入哈希表中。暴力枚举i{\in}\lbrack1,m\rbrack，到哈希表查询a^{im}，有k就输出

EX_BSGS：

还有一个加强版的BSGS在等着你

给定a，p，b，求最小整数解x，满足a^x{\equiv}\;b\;(mod\;p)。

由于没有互质关系，需要构造。

此时可以设g=gcd(a,p)

证明g是b的一个因子：

方程变为\frac{a^x}{g}\equiv\;\frac{b}{g}\;(mod\;\frac{p}{g})（模的分配率）

观察一下发现当g\;{\nmid}\;b并且b\not=1时，方程无解

所以设A=\frac{a}{g},P=\frac{g}{p}，于是有a=A\;{\times}\;g,p=P\;{\times}\;g

代入后变成了(Ag)^x\equiv\;b\;(mod\;Pg)

A^xg^x+yPg=b

提出一个g得g(A^xg^{x-1}+yP)=b

所以g就是b的因子，所以b=1时，a^0=1，其他情况当g\;{\nmid}\;b时，方程无解

于是可以把式子化成a^{x-1}\times\frac{a}{g}\equiv\;\frac{b}{g}\;(mod\;\frac{p}{g})

因为\frac{p}{g}比p小，所以可以约分到a，\frac{p}{g}互质

设sa=\prod_{i=1}^{k}\frac{a}{g_i}

所以a^{x-k}\equiv\;\frac{b}{\prod_{i=1}^{k}gsa}\;(mod\;\frac{p}{\prod_{i=1}^{k}g})

最后化出来应该是\frac{a}{\prod_{i=1}^{k}g}和\frac{p}{\prod_{i=1}^{k}g}互质

分析结束

代码我就忽略了哈

引例2

P4008 [NOI2003]文本编辑器

这道题目涉及到了更多操作，出现了一些问题。

插入时，如果y长度十分巨大，操作复杂度会退化。这时候，我们可以将插入的串分块，变为一个链表，之后把它插入原来的链表。

问题又来了——分出的块中有可能会有长度非常短的块，这时候就需要用到合并操作了。考虑插入串的左右端点，如果两端块长度小于规定分块的长度，就可以合并。

有时不一定是在完整的块后面插入，也有可能是在块内的某个元素后面插入。可以运用查询、分裂操作，把插入位置变成一个完整块的末尾，再进行插入即可。

void insert(int x,int l, char *s){
    int n = pos(x),next = n,tot = 0,t;
    split(n,x);
    while(tot+MAXS<=l){
        t=new_node();
        ins(next,t,MAXS,s+tot);
        next=t;
        tot+=MAXS;
    }
    if(tot<l){
        t=new_node();
        ins(next,t,l-tot,s+tot);
    }
    if(t!=-1&&a[next].szl+a[t].szl<MAXS){
        mesh(next,t);
    }
    if(a[n].next!=-1&&a[n].szl+a[a[n].next].szl<MAXB){
        mesh(n,a[n].next);
    }
}

还有一个新的操作——删除。例如删除[x,y]之间的序列，可将两端分裂，直接删除。

void erase(int x,int l){
    int n=search(x);
    split(n,x);
    int next=a[n].next;
    while(next!=-1&&l>=a[next].szl){
        l-=a[next].szl;
        next=a[next].next;
    }
    if(next!=-1){
        split(next,l);
        next=a[next].next;
    }
    for(int i=a[n].next;i!=next;i=a[n].next){
        a[now].nxt = a[i].nxt;
        del(i);
    }
    while(next!=-1&&a[n].szl+a[next].szl<MAXS){
        mesh(n,next);
        next=a[next].next;
    }
}

还有查询操作：

void find(int x,int l){
    int n=search(x),tot=min(a[n].sz-x,l);
    memcpy(ans,a[n].s+x,tot);
    int next=a[n].next;
    while(next!=-1&&l>=a[next].szl+tot){
        memcpy(ans+tot,a[next].s,a[next].szl);
        tot+=a[next].szl;
        next=a[next].next;
    }
    if(next!=-1&&tot<l){
        memcpy(ans+tot,a[next].s,l-tot);
    }
    ans[l]='\0';
    cout<<ans;
}

把这些操作像链表一样串在一起就好啦（雾

总结

引例1侧重用分块思想解决数学问题；

引例2侧重实打实地用块状链表这一数据结构解决问题。

4.写在最后

在题库中搜索“块状链表,块状数组,分块”，看到更多你想要的~（就像这样啦）