分散层叠算法学习笔记

杂项 学习笔记

更好的阅读体验

前言

分散层叠算法，英文为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$）：

• $i=k$时，$b_i=a_i$。
• $i<k$时，$b_i$是$a_i$和$b_{(i+1),(2\cdots \lfloor\frac{len_{i+1}}{2}\rfloor)}$归并排序的结果。
• 归并排序的同时，顺便维护出$b_i$中每个元素在$a_i,b_{i+1}$中的后继$pos,lst$。

不难得到$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，跳表等算法/数据结构中，但劣势是实现的细节过多。

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

参考资料

分散层叠算法学习笔记——Dpair

题解 P6466 【分散层叠算法(Fractional Cascading)】——AThousandSuns