分散层叠算法学习笔记

· · 个人记录

更好的阅读体验

前言

分散层叠算法，英文为Fractional Cascading，可以以优秀的时空复杂度在线计算出某个值在若干个序列中后继。

Fractional意为分散的，Cascading意为阶梯式渗透，而Fractional Cascading本质上就是对于若干个有序信息分散开，然后一层层渗透，然后得到最后的结果。

模板

P6466 分散层叠算法(Fractional Cascading)

给定k个长度为n的有序数组，q次查询某个数x的非严格后继。（1\leqslant k\leqslant 100,1\leqslant n\leqslant 10^4,1\leqslant q\leqslant 5\times 10^5）

注意，下面的后继都指的是非严格后继。

首先有一个很简单的时间O(nk+qk\log n)空间O(nk)做法，即对于每个序列都二分一遍。

还有一种做法是时间O(nk^2+q\log (nk))空间O(nk^2)的，也就是将k个序列归并排序成为一个长度为nk的序列，每个位置维护它在每个序列中的后继，询问在大序列里二分。

考虑综合两个方法分别的优势，得到更优秀的做法。

设k个序列为a_{1\cdots k}，我们按下面的方法构造k个序列b_{1\cdots k}（设b_i长度为len_i）：

不难得到len_i=n+\lfloor\frac{len_{i+1}}{2}\rfloor，即有len_i<2n，于是预处理的时空复杂度为O(nk)。

查询的时候，我们在b_1内二分得到x的后继位置p，则p的pos为x在a_k内的后继。

考察p的lst与x在b_2内的后继之间的距离d，若其大于1，则有b_{2,p_{lst}-2}\geqslant x，则b_1存在一个不大于p的值在p的前面，与p是x的后继矛盾，因此d\leqslant 1。

那么我们直接暴力检查p_{lst}之前一个位置，判断它是否更优就可以得到x在b_2内的后继。

以此类推，查询的总复杂度为O(q(k+\log n))。

#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=20005,maxk=105;
int n,k,q,d,lastans;
int a[maxk][maxn],len[maxk],c[maxn];
struct node{
    int val,pos,lst;
}b[maxk][maxn],tmp[maxn];
int main(){
    scanf("%d%d%d%d",&n,&k,&q,&d);
    for(int i=1;i<=k;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    len[k]=n;
    for(int i=1;i<=n;i++)
        b[k][i].val=a[k][i],b[k][i].pos=i,b[k][i].lst=0;
    for(int i=k-1;i>=1;i--){
        for(int j=2;j<=len[i+1];j+=2)
            tmp[j/2]=b[i+1][j],tmp[j/2].lst=j;
        int ptmp=1,plst=1;
        for(int j=1;j<=n;j++){
            while(ptmp<=len[i+1]/2&&tmp[ptmp].val<=a[i][j])
                len[i]++,b[i][len[i]]=tmp[ptmp],b[i][len[i]].pos=j,ptmp++;
            while(plst<=len[i+1]&&b[i+1][plst].val<a[i][j])
                plst++;
            len[i]++,b[i][len[i]].val=a[i][j],b[i][len[i]].pos=j,b[i][len[i]].lst=plst;
        }
        while(ptmp<=len[i+1]/2)
            len[i]++,b[i][len[i]]=tmp[ptmp],b[i][len[i]].pos=n+1,ptmp++;
    }
    for(int i=1;i<=len[1];i++)
        c[i]=b[1][i].val;
    for(int i=1;i<=q;i++){
        int x,pos;
        scanf("%d",&x),x^=lastans,pos=lower_bound(c+1,c+len[1]+1,x)-c;
        lastans=0;
        for(int i=1;i<=k;i++){ 
            if(pos>1&&b[i][pos-1].val>=x)
                pos--;
            if(pos<=len[i])
                lastans^=a[i][b[i][pos].pos],pos=b[i][pos].lst;
            else pos=len[i+1]+1;
        }
        if(i%d==0)
            printf("%d\n",lastans);
    }
    return 0;
}

扩展

在一个每个点度数不超过d的DAG上，每个节点x存在一个长度为n的有序序列a_x，每次查询x在一条链上每个点对应的序列中的后继。

不难发现模板的内容是DAG是一条链的情况。

该问题的解法法类似于模板，考虑在拓扑排序中每遇到一个x\rightarrow y，就让b_x的\frac{1}{d}归并入b_y（没有入度的点b_x=a_x），每次询问从x的信息得到y的信息的时候可以二分查找做到k\log d+\log (dn)。

此时点x的最劣长度是不大于到达x的点长度最大值的\frac{d-1}{d}加n，即每个点长度最大值是趋近于数列l_i=\begin{cases}n&i=1\\\frac{d-1}{d}l_{i-1}+n&i>1\end{cases}的极限的。

把所有l_i除以n就可以发现l拆开就是等比数列求和的形式：\frac{l_i}{n}=1+\frac{d-1}{d}+(\frac{d-1}{d})^2+(\frac{d-1}{d})^3+\cdots

等比数列求和可得\lim_{i\rightarrow \infty}l_i=dn

于是这个做法的时间复杂度为O(dnk+q\log d(k+\log n))，空间复杂度为O(dkn)的。视d为常数时复杂度为O(nk+q(k+\log n))。

本质

实际上，上文中提取\frac{1}{d}的信息是一种误差的思想（似乎在Dpair的博客内称为扰动系数）

我们考虑对于若干个序列进行分散层叠时，可以从每个序列提取\frac{1}{d}的信息，做一遍分散层叠，最后直接用二分找到真实的位置，这样分散层叠复杂度会变为O(\frac{nk}{d}+q(k\log d+\log n))，这个改变有助于我们在某些题目中平衡算法的时间复杂度，减小算法的空间复杂度。（还可以在线处理）

应用

例题1

区间加，区间查询一个数x的排名。

首先考虑一个很简单的做法：枚举每个块，在块内二分出小于x的数的个数，复杂度为O(n\sqrt{n}\log n)。

序列分块，设块长为B，误差为d，再设一个阈值S表示每S个块拉出来\frac{1}{d}跑一次分散层叠，那么我们一共跑了\frac{n}{BS}个分散层叠（预处理复杂度O(\frac{n}{BS}\times\frac{BS}{d}=\frac{n}{d})）。（这类似于在分块的基础上继续分块）

对于第一层的整块，询问直接合并分散层叠（复杂度为O(\frac{n}{BS}\times (S\log d+\log B)=O(\frac{n}{B}\log d+\frac{n}{BS}\log B)）修改对应的整块打标记（复杂度O(\frac{n}{B})），对应的散块暴力重构，这样的复杂度为O(\frac{BS}{d})的。

对于第一层的散块（同时也是第二层的整块）暴力建分散层叠可以做到O(\frac{BS}{d}+S\log d+\log B)

对于第二层的散块跑暴力，复杂度为O(B)。

总体复杂度为O(\frac{n}{B}\log d+\frac{n}{BS}\log B+\frac{BS}{d}+B)。

经过计算可得B=\sqrt{n\log\log n},d=S=\log n时复杂度为O(\sqrt{n\log\log n})。

这种方法复杂度可以更小，但是没有实际意义了。

我们发现上面的方法是分块上分块的结果，于是很自然地想到分更多层，即利用线段树的结构进行更多层分块。

我们对\frac{n}{B}个块建立线段树，每个非叶子节点存储两个儿子\frac{1}{d}信息的归并。

对于区间修改，仍然采用整块打标记散块重构的方式，不难发现散块重构需要修改散块对应节点到线段树根节点这条路径的所有点代表的序列，序列长度之和为B+\frac{2}{d}B+\frac{4}{d^2}B+\cdots=B\sum_{i=1}^{\log\frac{n}{B}}(\frac{2}{d})^i，当d>2时一次修改复杂度变为了O(B)。

对于区间查询，我们在根节点二分出位置，然后暴力递归儿子，由于线段树的结构，共有O(\frac{n}{B})个节点，每个节点的误差需要O(d)的时间调整，于是一次询问复杂度为O(\frac{nd}{B}+\log n)，d越小复杂度越小。

当d=3,B=\sqrt{n}时复杂度明显最优，此时时间复杂度O((n+q)\sqrt n)，空间复杂度O(n)，极其优秀。

例题2

区间加，区间查询第k大。

即P5356 [Ynoi2017] 由乃打扑克。

例题3

区间加，单点修改，区间查询最大值小于等于值x的子区间数量。

即P6578 [Ynoi2019] 魔法少女网站。

例题4

区间加，区间查询最大子段和。

即P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？。

后记

分散层叠算法适用于在线算法时间复杂度的平衡以及空间复杂度的减小，在分块问题上有着广泛的应用，其思想也应用在了range tree，跳表等算法/数据结构中，但劣势是实现的细节过多。

所以做分散层叠口胡就行了，比赛还是用别的方法吧。