浅谈基于 FHQ-Treap 实现的单 log LCT

· · 算法·理论

前言

最近想学 \texttt{LCT}，但是发现自己不会 \texttt{Splay}，但又不想学 \texttt{Splay}，于是我学习了 \texttt{FHQ-Treap} 写 \texttt{LCT}，但是是两只 \log 的。最近又在网上水到了优化至单 \log 版本的，又发现洛谷上几乎没有讲这个东西的文章，所以决定自己写一篇。

阅读本文前，请保证已掌握 \texttt{FHQ-Treap}，最好还有一些 \texttt{LCT} 基础。

\texttt{FHQ-Treap} 写 双 \log \texttt{LCT}

首先我们先来看一下 \texttt{LCT} 到底在干什么。

考虑如何用 $\texttt{FHQ-Treap}$ 来维护实链。我们把实链上的每个点按深度从小到大的顺序加入 $\texttt{Treap}$，即 $\texttt{Treap}$ 中序遍历顺序就是节点在实链中从上到下的深度顺序。 这样用 $\texttt{FHQ-Treap}$ 维护一些基本信息就没有问题了，现在考虑如何实现 $\text{access}(x)$ 操作。 $\text{access}(x)$ 的目标是让从根到 $x$ 的路径成为一条实链。过程中需要不断地将实链“一分为二”或“合二为一”，然后我们惊奇地发现 $\texttt{FHQ-Treap}$ 的 $\text{split}$ 和 $\text{merge}$ 和这两个东西十分般配，于是考虑魔改一下。 ### $\text{\textbf{split}} 换另一个思路。由于我们是按 $\texttt{Treap}$ 中具体的某个点来分，所以我们可以去寻找分裂路径。对每个点 $u$ 维护 $\text{fa}_u$，指 $u$ 在 $\texttt{Treap}$ 中的父亲。当以 $u$ 分裂时，顺着 $\text{fa}$ 一直向上走到根并记录路径，再从根开始依照记录的路径向下不断分裂，直到走到 $u$。具体实现看代码： ```cpp bool isrt(int u){return (lc[fa[u]]!=u&&rc[fa[u]]!=u)||!fa[u];} //发现 fa[u] 并不好清理，所以加上 lc[fa[u]]!=u&&rc[fa[u]]!=u 辅助判断 int findrt(int u){ for(top=0;!isrt(u);u=fa[u]) st[++top]=(lc[fa[u]]==u); //仅记录往左还是往右，不记录具体点 return u; } void split(int u,int&l,int&r){ if(!top){ pushdown(u); l=u,r=rc[u],rc[u]=0; pushup(u); //注意 u 本身被分在上半部分 return ; } bool d=st[top--]^tag[u]; //消除翻转标记的影响（makert需要） pushdown(u); if(d)r=u,split(lc[u],l,lc[u]); else l=u,split(rc[u],rc[u],r); pushup(u); } //调用 split 时直接 split(findrt(u),x,y) ``` ### $\text{\textbf{merge}}

和普通 \texttt{FHQ-Treap} 一样，保证传入顺序正确即可。

int merge(int l,int r){
    if(!l||!r)return l|r;
    if(tr[l].k<tr[r].k)return pushdown(l),rc[l]=merge(rc[l],r),pushup(l),l;
    else return pushdown(r),lc[r]=merge(l,lc[r]),pushup(r),r;
}

\text{\textbf{access}}

现在考虑如何记录虚边。这里我们需要一个数组 $\text{fb}$ 记录从当前实链往上跳一个虚边会跳到哪个点。但又有个问题，就是一条实链的 $\text{fb}$ 应记在实链的哪个点上。这里我们选择链顶（即 $\texttt{Treap}$ 的最左点）而不是 $\texttt{Treap}$ 的根。因为这样能保证在 $\text{split}$ 后这个 $\text{fb}$ 能够保持在上半部分而不是变到下面去了。（好像放根上也行，但 $\text{split}$ 要返回 $\text{fb}$？） 注意在连接/断开实链时的同时要维护虚边。 ```cpp //顺着左儿子找最左点，先跑回根可以避免一些玄学错误 int findleft(int u){ u=findrt(u),pushdown(u); for(;lc[u];u=lc[u],pushdown(u)); return u; } int access(int u){ int last=0;//last,tp,bt 都存的是根 for(int tp,bt;u;u=fb[findleft(last)]){ split(findrt(u),tp,bt); fb[findleft(last)]=0; fb[findleft(bt)]=u; //记得维护虚边 last=merge(tp,last); } return last; } ``` 有了 $\text{access}$ 后其它操作就可以迎刃而解了。 ### 复杂度分析 $\texttt{LCT}$ 的大多数操作都建立在 $\text{access}$ 的基础上，而其它东西的复杂度都没有 $\text{access}$ 高，所以主要分析 $\text{access}$ 的复杂度。 Sleator 和 Tarjan 告诉我们 $\text{access}$ 经过的 虚边/实链 数量是均摊 $O(\log n)$ 的（$n$ 为动态树/森林节点数，下同）。而在这里，每经过一条实链都要对对应 $\texttt{Treap}$ 进行 $\text{split,merge,findleft,findrt}$ 这四种操作，最坏复杂度均为期望 $O(\log n)$。 综上，两者相乘，得到该做法单次 $\text{access}$ 的时间复杂度为**期望均摊** $O(\log^2 n)$。 但是实际上一般情况下每次被操作 $\texttt{Treap}$ 的大小都不到 $n$，再加上 $\texttt{FHQ-Treap}$ 本身常数就比 $\texttt{Splay}$ 小，若在其它地方再卡卡常就和用 $\texttt{Splay}$ 写的差不多了。 ## $\texttt{FHQ-Treap}$ 写 单 $\log$ $\texttt{LCT}

前面那个 O(\log n) 的经过实链数显然无法优化的，所以我们考虑优化 \text{split} 和 \text{merge}。

我们发现若当前是按 u 分裂，设 u 在当前 \texttt{Treap} 中的深度为 d_u，那 \text{split} 只需要迭代 d_u 次就结束了。但在原来的 \texttt{Treap} 中 d_u 是 O(\log n)，于是我们去想如何减少 d_u 的量级。

这时我们需要用到一个叫做 加权 \texttt{Treap} 的东西。实际上就是为每个节点 u 额外赋予一个固定权值 w_u。然后，把 u 在 \texttt{Treap} 里的优先级定为“w_u 个随机数的最大值”，而不是一个固定的随机键值。然后我们有个结论：

:::align{center} 若点 u 在一棵权值和为 S 的 加权 \texttt{Treap} 里，其期望深度为 O(\log \dfrac{S}{w_u})。 :::

这个东西可以用概率论算，此处就不详细展开说明了。（其实是我不会）

发现若沿用上一部分的实现，\text{split,\;findrt} 这两种操作已经可以做到 O(\log \dfrac{S}{w_u}) 了，但 \text{merge,} \text{findleft} 还不行。所以现在我们需要对它们进行再次魔改。

在这里，我们需要用到 \text{3-way} 的 \text{split,merge}。注意 \text{split} 也要改，这是为了方便 \text{merge} 的实现。

{\text{\textbf{3-way split}}}

所谓 \text{3-way split}，就是在原来的 \text{split} 上把 u 给单独拎出来，而不是与上半部分分一起。具体看代码：

void split(int u,int&l,int&r){
    if(!top){
        pushdown(u);
        l=lc[u],r=rc[u],lc[u]=rc[u]=0;
        //只有这有区别
        pushup(u);
        return ;
    }
    bool d=st[top--]^tag[u];
    pushdown(u);
    if(d)r=u,split(lc[u],l,lc[u]);
    else l=u,split(rc[u],rc[u],r);
    pushup(u);
}

{\text{\textbf{3-way merge}}}

相应的，{\text{3-way merge}} 就是将左边一段、中间的点 u、右边一段这三部分合一起。这样，当本次迭代需要 u 当根了，就可以直接把左边的和右边的变为 u 的左右儿子，并结束 \text{merge}。这样就能保证 O(\log \dfrac{S}{w_u}) 的复杂度。

在实际实现中，我们也不需要真的算出 w_u 个随机数，这样太笨了。设 \text{sz}_u= \sum_{v\in \text{subtree}(u)}w_v，然后根据 \text{sz}_u 的大小比重来随机选择根，可以证明是等价的。具体看代码：

int merge(int l,int u,int r){
    if(!l&&!r)return lc[u]=rc[u]=0,pushup(u),u;
    int d=rd()%(sz[l]+wt[u]+sz[r]);
    if(d<sz[l])return pushdown(l),rc[l]=merge(rc[l],u,r),pushup(l),l;
    else if(d<sz[l]+wt[u])return lc[u]=l,rc[u]=r,pushup(u),u;
    else return pushdown(r),lc[r]=merge(l,u,lc[r]),pushup(r),r;
}

\text{\textbf{findleft}}

显然不能去暴力找了，于是我们对 \texttt{Treap} 中每个点 u 维护 \text{ly}_u 和 \text{ry}_u，分别表示 u 子树中最左的点和最右的点，记录最右的点是因为有翻转操作。每次 \text{pushdown} 和 \text{pushup} 的时候及时更新即可。

查询时若是根直接 O(1) 查表，否则先 \text{findrt} 再查表。

void updyy(int u){
    ly[u]=(lc[u]?ly[lc[u]]:u),ry[u]=(rc[u]?ry[rc[u]]:u);
    if(tag[u])swap(ly[u],ry[u]);
}
void pushup(int u){
    updyy(u);
    sz[u]=sz[lc[u]]+wt[u]+sz[rc[u]];//上文提到的子树权值和
    if(lc[u])fa[lc[u]]=u;if(rc[u])fa[rc[u]]=u;
}
void pushdown(int u){
    if(!tag[u])return ;
    swap(lc[u],rc[u]),tag[u]=0;
    if(lc[u])tag[lc[u]]^=1,updyy(lc[u]);
    if(rc[u])tag[rc[u]]^=1,updyy(rc[u]);
    updyy(u);
}

现在考虑如何设置 w_u 以优化复杂度。

定义 \text{siz}_u 为 u 在原树中的子树大小。令 w_u=(\sum_{v为u的虚儿子}\text{siz}_v)+1，就可以让单次 \text{access} 的时间复杂度达到期望均摊 O(\log n)。

由于 \texttt{LCT} 的 \text{access,link,cut} 等操作都会使 u 的虚子树发生改变，所以需要特别注意 w_u 的维护上的细节，很多小地方不小心写错都会使复杂度退化。

复杂度分析

设在一次 \text{access} 共经过 k 条实链，其中沿虚边所跳到的点从下到上依次为 u_0,u_1,u_2,\dots,u_k （实链按这些点断开，u_0 是起始点）。u_i 在 \text{access} 前的权值为 w'_{u_i}，在 \text{access} 后的权值为 w''_{u_i}。u_i 所在的实链所对应的 \texttt{Treap} 为 T_i，T_i 对应实链的链顶为 t_i。不难发现 T_i 中所有节点的权值和等于 \text{siz}_{t_i}。

先考虑 \text{split} 和 \text{findrt} 的代价。

已知 \text{access} 中对第 i 条实链进行这两种操作的代价均为期望 O(\log \dfrac{\text{siz}_{t_i}}{w'_{u_i}})。

此时 t_{i-1} 就是 u_{i} 的一个虚儿子，所以 w'_{u_{i}}\ge \text{siz}_{t_{i-1}}（w'_{u_0}\ge 1），于是可以得到：

\sum_{i=0}^k O(\log \dfrac{\text{siz}_{t_i}}{w'_{u_i}})\le O(\log \text{siz}_{t_0})+\sum_{i=1}^k O(\log \dfrac{\text{siz}_{t_i}}{\text{siz}_{t_{i-1}}}) = O(\log \text{siz}_{t_k})\le O(\log n)

所以单次 \text{access} 中 \text{split} 和 \text{findrt} 的总代价为期望 O(\log n)。

现在考虑 \text{merge} 的代价。

因为 \text{access} 中对第 i 条实链进行 \text{merge} 的代价为期望 O(\log \dfrac{\text{siz}_{t_i}}{w''_{u_i}})，而 w''_{u_i} 不一定满足 w''_{u_{i}}\ge \text{siz}_{t_{i-1}}，所以无法再像之前一样直接算，需要使用势能转化一下：

定义全局势能函数为森林中所有节点权值的对数和：\Phi = \sum_{x=1}^n \log_2 w_x \in [0, n \log_2 n]。

在 \text{access} 的第 i 步中，全图只有 w_{u_i} 发生了改变。势能变化量 \Delta \Phi_i = \log_2 w''_{u_i} - \log_2 w'_{u_i} = \log_2 \dfrac{w''_{u_i}}{w'_{u_i}}。于是第 i 步中 \text{merge} 的均摊耗时就是 ：

\log_2 \dfrac{\text{siz}_{t_i}}{w''_{u_i}}+\Delta \Phi_i=\log_2 \dfrac{\text{siz}_{t_i}}{w''_{u_i}}+ \log_2 \dfrac{w''_{u_i}}{w'_{u_i}}=\log_2 \dfrac{\text{siz}_{t_i}}{w'_{u_i}}

化成这样之后的分析就和 \text{split} 一样了，所以单次 \text{access} 中 \text{merge} 的总耗时为期望均摊 O(\log n)。

还有一部分是跳虚边等其他操作的代价，而这些操作在 \text{access} 的每步中都是 O(1) 的，而 \text{access} 的操作步数为均摊 O(\log n) 的。所以这一部分的总代价为均摊 O(\log n)。

综合以上三部分的代价，可得该做法单次 \text{access} 的复杂度为期望均摊 O(\log n)。

但是该做法的常数巨大，在 P3690 甚至跑不过上面的双 \log 做法。可能在极端数据下单 \log 的优势才能展示出来。

完整代码

以下为 P3690 分别使用这两种做法的所写的代码，以供参考。（码风略丑）

::::success[双 \log 做法]

#include<bits/stdc++.h>
using namespace std;
unsigned seed=0x9e3779b9;
unsigned rd(){seed^=seed<<13,seed^=seed>>17,seed^=seed<<5;return seed;}
const int N=3e5+5;
struct LCT{
    struct{int v,k;}tr[N];
    int lc[N],rc[N],fa[N],fb[N],tag[N],xr[N],st[N],top;
    void pushdown(int u){
        if(!tag[u])return;
        swap(lc[u],rc[u]),tag[u]=0;
        tag[lc[u]]^=1,tag[rc[u]]^=1;
    }
    void pushup(int u){
        xr[u]=tr[u].v^xr[lc[u]]^xr[rc[u]];
        if(lc[u])fa[lc[u]]=u;if(rc[u])fa[rc[u]]=u;
    }
    bool isrt(int u){return (lc[fa[u]]!=u&&rc[fa[u]]!=u)||!fa[u];}
    int findrt(int u){
        for(top=0;!isrt(u);u=fa[u])
            st[++top]=(lc[fa[u]]==u);
        return u;
    }
    int findleft(int u){
        u=findrt(u),pushdown(u);
        for(;lc[u];u=lc[u],pushdown(u));
        return u;
    }
    void split(int u,int&l,int&r){
        if(!top)return pushdown(u),l=u,r=rc[u],rc[u]=0,pushup(u),void();
        bool d=st[top--]^tag[u];
        pushdown(u);
        if(d)r=u,split(lc[u],l,lc[u]);
        else l=u,split(rc[u],rc[u],r);
        pushup(u);
    }
    int merge(int l,int r){
        if(!l||!r)return l|r;
        if(tr[l].k<tr[r].k)return pushdown(l),rc[l]=merge(rc[l],r),pushup(l),l;
        else return pushdown(r),lc[r]=merge(l,lc[r]),pushup(r),r;
    }
    int access(int u){
        int last=0;
        for(int tp,bt;u;u=fb[findleft(last)]){
            split(findrt(u),tp,bt);
            fb[findleft(last)]=0;
            last=merge(tp,last);
            fb[findleft(bt)]=u;
        }
        return last;
    }
    void makert(int u){tag[access(u)]^=1;}
    void link(int u,int v){makert(u),fb[u]=v;}
    void cut(int u,int v){makert(u),access(v),access(u),fb[v]=0;}
    int query(int u,int v){return makert(u),xr[access(v)];}
    void update(int u,int v){tr[u].v=v;for(;!isrt(u);u=fa[u])pushup(u);pushup(u);}
    int root(int u){return findleft(access(u));}
    bool check(int u,int v){return root(u)==root(v);}
    void newnode(int p,int v){
        tr[p]={v,(int)rd()},xr[p]=v;
        lc[p]=rc[p]=fa[p]=fb[p]=tag[p]=0;
    }
}lct;
int n,m;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1,v;i<=n;i++)
        cin>>v,lct.newnode(i,v);
    for(int op,u,v;m--;){
        cin>>op>>u>>v;
        if(op==0)cout<<lct.query(u,v)<<"\n";
        if(op==1&&!lct.check(u,v))lct.link(u,v);
        if(op==2&&lct.check(u,v))lct.cut(u,v);
        if(op==3)lct.update(u,v);
    }
    return 0;
}

::::

AC 记录，总耗时 1.06s，最大耗时 437ms。

::::success[单 \log 做法]

#include<bits/stdc++.h>
using namespace std;
unsigned seed=0x9e3779b9;
unsigned rd(){seed^=seed<<13,seed^=seed>>17,seed^=seed<<5;return seed;}
const int N=1e5+5;
struct LCT{
    int tr[N],lc[N],rc[N],ly[N],ry[N],fa[N],fb[N],tag[N],xr[N],wt[N],sz[N],st[N],top;
    void updyy(int u){
        ly[u]=(lc[u]?ly[lc[u]]:u),ry[u]=(rc[u]?ry[rc[u]]:u);
        if(tag[u])swap(ly[u],ry[u]);
    }
    void pushup(int u){
        updyy(u);
        xr[u]=xr[lc[u]]^tr[u]^xr[rc[u]];
        sz[u]=sz[lc[u]]+wt[u]+sz[rc[u]];
        if(lc[u])fa[lc[u]]=u;if(rc[u])fa[rc[u]]=u;
    }
    void pushdown(int u){
        if(!tag[u])return ;
        swap(lc[u],rc[u]),tag[u]=0;
        if(lc[u])tag[lc[u]]^=1,updyy(lc[u]);
        if(rc[u])tag[rc[u]]^=1,updyy(rc[u]);
        updyy(u);
    }
    bool isrt(int u){return !fa[u]||(lc[fa[u]]!=u&&rc[fa[u]]!=u);}
    int findrt(int u){
        for(top=0;!isrt(u);u=fa[u])
            st[++top]=(lc[fa[u]]==u);
        return u;
    }
    void split(int u,int&l,int&r){
        if(!top)pushdown(u),l=lc[u],r=rc[u],lc[u]=rc[u]=0;
        else{
            bool d=st[top--]^tag[u];
            pushdown(u);
            if(d)r=u,split(lc[u],l,lc[u]);
            else l=u,split(rc[u],rc[u],r);
        }
        pushup(u);
    }
    int merge(int l,int u,int r){
        if(!l&&!r)return lc[u]=rc[u]=0,pushup(u),u;
        int d=rd()%(sz[l]+wt[u]+sz[r]);
        if(d<sz[l])return pushdown(l),rc[l]=merge(rc[l],u,r),pushup(l),l;
        else if(d<sz[l]+wt[u])return lc[u]=l,rc[u]=r,pushup(u),u;
        else return pushdown(r),lc[r]=merge(l,u,lc[r]),pushup(r),r;
    }
    int access(int u){
        int last=0;
        for(int tp,bt,tmp;u;u=fb[ly[last]]){
            split(findrt(u),tp,bt);
            if(tmp=ly[last])fb[tmp]=0,wt[u]-=sz[last];
            if(tmp=ly[bt])fb[tmp]=u,wt[u]+=sz[bt];
            last=merge(tp,u,last);
        }
        return last;
    }
    void makert(int u){int rt=access(u);tag[rt]^=1,updyy(rt);}
    void upd(int u){int x,y;split(findrt(u),x,y),merge(x,u,y);}
    void link(int u,int v){makert(u),makert(v),fb[v]=u,wt[u]+=sz[findrt(v)],upd(u);}
    void cut(int u,int v){
        makert(u),access(v),access(u);
        if(fb[v])fb[v]=0,wt[u]-=sz[findrt(v)],upd(u);
    }
    int query(int u,int v){return makert(u),xr[access(v)];}
    void update(int u,int v){tr[u]=v;for(;!isrt(u);u=fa[u])pushup(u);pushup(u);}
    int root(int u){return ly[findrt(access(u))];}
    bool check(int u,int v){return root(u)==root(v);}
    void newnode(int p,int v){
        tr[p]=xr[p]=v,ly[p]=ry[p]=p,wt[p]=sz[p]=1;
        fa[p]=fb[p]=lc[p]=rc[p]=tag[p]=0;
    }
}lct;
int n,m;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1,v;i<=n;i++)
        cin>>v,lct.newnode(i,v);
    for(int op,u,v;m--;){
        cin>>op>>u>>v;
        if(op==0)cout<<lct.query(u,v)<<"\n";
        if(op==1&&!lct.check(u,v))lct.link(u,v);
        if(op==2&&lct.check(u,v))lct.cut(u,v);
        if(op==3)lct.update(u,v);
    }
    return 0;
}

::::

AC 记录，总耗时 1.28s，最大耗时 584ms。

参考资料

  1. 《Dynamic Trees with Alternative Search Trees》 by riteme
  2. 《用无旋转 Treap 来写 LCT》 by immortalCO
  3. 《FHQ&LCT》 by a1a2a3a4a5
  4. 《用 Treap 实现的单 log LCT》 by lgswdn_SA

AI 使用说明：本文在复杂度分析部分使用了 Deepseek 和 Gemini 辅助完成，其他内容均由真人完成。

若文章内容有误，欢迎大家指出，我会尽快做出修改 QwQ。