首页 > 其他分享 >全局平衡二叉树

全局平衡二叉树

时间：2022-10-18 08:34:47浏览次数：82  
标签：Heavy typedef return Siz Fath uint 二叉树 平衡 全局

全局平衡二叉树，其实说白了就是在树链剖分的基础上再次对每条链以相对平衡的方法再次重构成一颗固态的二叉树的形态，或者说在 LCT 的基础上把 Splay 换成满足全局平衡的二叉树，然后每步暴力往上跳即可。

以下是详细思想。

考虑 LCT 在静态树上常数很大，很大程度上是因为其 splay/access/makeroot 次数太多了。

如果我们能在 LCT 中按照一种合适的方法重建 Splay 的结构，把 Splay 换成某种静态的二叉树结构，则不用做 splay/access/makeroot 操作了，直接暴力跳父亲即可。

怎么换呢？

一种简单的想法是把每条链重构成一颗单独的线段树/静态平衡 BST。

这个东西其实就和普通的树剖区别不大了……单点修改/链查询复杂度容易发现是单次 \(O(\log^2n)\) 的。

为什么这个东西是两只老哥的呢？

因为在每条链上，平均每个节点的高度是 \(O(\log n)\) 的，而且这个东西可以被毒瘤出题人把 \(O(\log n)\) 条取满老哥的链首尾相接成链然后询问……

考虑如何避免出现这种几个取满老哥的位置首尾相接的毒瘤情况。

注意到平衡二叉树构造时是直接取中点拆成左右两段区间递归下去的，我们觉得这不好；一部分节点子树很大，你应该在这个点这里把它挪的高一点，避免在这里取满老哥。

考虑到中点其实就是一条链的重心，我们要把子树大小作为一个决定谁高谁低的指标的话，就应当求这条链的带权重心；原来求出的平衡二叉树就是一条链的点分树，而我们需要的全局平衡二叉树就是一条链的带权点分树，其中每个节点所在的子树对应重链上的一段区间。这点就和 Splay 维护 LCT 类似了。

因此算法流程就出来了：

  1. 进行轻重链剖分，把每条链提取出来。
  2. 对每个结点按轻子树大小之和定点权。
  3. 对每条重链，求出其带权点分树，即全局平衡二叉树。
  4. 对每条轻边，按类似 LCT 的方式，儿子认父亲，父亲不认儿子。
  5. 每条链的信息在平衡树上维护，单点修改/链查询直接暴力跳就好了。

这样，整个算法就完成啦！

容易证明，在这种结构上，树的高度是 \(O(\log n)\) 的，于是就完了。

当然，在随机数据下，这个算法实际运行效率和树剖差别不大……甚至有的时候常数还更大……

不过，如果使用这个算法来分治，我们就可以叫做树的链分治了。

习题：

代码咕咕。

动态树分治那题实现了一下。

下面是未经卡常的慢爆了的代码。

Code 
#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
llt inf=1e18;
struct Mat{
    llt A[2][2];
    Mat():A{{-inf,-inf},{-inf,-inf}}{}
    llt*operator[](uint n){return A[n];}
    friend Mat operator*(Mat a,Mat b){
        Mat ans;
        for(uint i=0;i<2;i++)for(uint j=0;j<2;j++)for(uint k=0;k<2;k++)_max(ans[i][k],a[i][j]+b[j][k]);
        return ans;
    }
};
uint Fath[1000005],Son[2][1000005];
std::vector<uint>Way[1000005];
uint Siz[1000005],Heavy[1000005],Siz2[1000005];
voi dfs(uint p,uint f){
    Siz[p]=1,Fath[p]=f,Heavy[p]=-1;
    for(auto s:Way[p])if(s!=f){dfs(s,p),Siz[p]+=Siz[s];if(!~Heavy[p]||Siz[s]>Siz[Heavy[p]])Heavy[p]=s;}
    Siz2[p]=Siz[p];if(~Heavy[p])Siz2[p]-=Siz[Heavy[p]];
}
llt G[1000005],H[1000005],V[1000005];
Mat W[1000005];
voi pushup(uint p){
    W[p][0][0]=W[p][0][1]=G[p];
    W[p][1][0]=H[p],W[p][1][1]=-inf;
    if(~Son[0][p])W[p]=W[Son[0][p]]*W[p];
    if(~Son[1][p])W[p]=W[p]*W[Son[1][p]];
}
uint build(uint l,uint r,std::vector<uint>&Ps){
    if(l>=r)return-1;
    uint siz=0,w=-1,wp=l;
    for(uint i=l;i<r;i++)siz+=Siz2[Ps[i]];
    for(uint i=l,s=0;i<r;i++){
        uint a=std::max(s,siz-s-Siz2[Ps[i]]);
        if(_min(w,a))wp=i;
        s+=Siz2[Ps[i]];
    }
    if(~(Son[0][Ps[wp]]=build(l,wp,Ps)))Fath[Son[0][Ps[wp]]]=Ps[wp];
    if(~(Son[1][Ps[wp]]=build(wp+1,r,Ps)))Fath[Son[1][Ps[wp]]]=Ps[wp];
    pushup(Ps[wp]);return Ps[wp];
}
uint build(uint p){
    std::vector<uint>A;while(~p)A.push_back(p),p=Heavy[p];
    for(auto p:A)for(auto s:Way[p])if(s!=Fath[p]&&s!=Heavy[p]){
        uint a=build(s);Fath[a]=p;
        G[p]+=std::max(W[a][0][0],W[a][1][0]),H[p]+=W[a][0][0];
    }
    return build(0,A.size(),A);
}
voi remove(uint p){
    std::vector<uint>A;
    while(~p){
        if(~Fath[p]&&p!=Son[0][Fath[p]]&&p!=Son[1][Fath[p]])
            G[Fath[p]]-=std::max(W[p][0][0],W[p][1][0]),H[Fath[p]]-=W[p][0][0];
        p=Fath[p];
    }
}
voi update(uint p){
    while(~p){
        pushup(p);
        if(~Fath[p]&&p!=Son[0][Fath[p]]&&p!=Son[1][Fath[p]])
            G[Fath[p]]+=std::max(W[p][0][0],W[p][1][0]),H[Fath[p]]+=W[p][0][0];
        p=Fath[p];
    }
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
#endif
    uint n,m;scanf("%u%u",&n,&m);
    for(uint i=0;i<n;i++)scanf("%lld",V+i),H[i]=V[i];
    for(uint i=1,u,v;i<n;i++)scanf("%u%u",&u,&v),Way[--u].push_back(--v),Way[v].push_back(u);
    dfs(0,-1);
    uint rot=build(0);
    Fath[rot]=-1;
    llt ans=0;
    while(m--){
        uint p;llt v;scanf("%u%lld",&p,&v),p=(p^ans)-1;
        remove(p);
        H[p]-=V[p],H[p]+=V[p]=v;
        update(p);
        printf("%lld\n",ans=std::max(W[rot][0][0],W[rot][1][0]));
    }
    return 0;
}

实现了一下切树游戏。

题解口胡一下。

我们先套路的 FWT 一下。

这样我们只用求出 \(m\) 个对应点的答案。

设 \(f_p\) 表示以当前点为根的联通子树的权值之和。

设 \(g_p\) 表示以当前点为根的子树中的联通子树的权值之和。

则 \(f_p=v_p\prod_s(1+f_s),g_p=f_p+\sum_sg_s\)。

设 \(h_p=v_p\prod_{\text{轻儿子}s}(1+f_s),u_p=\sum_{\text{轻儿子}s}g_s\)。

则 \(f_p=(1+f_{\text{重儿子}s})h_p,g_p=f_p+u_p+g_{\text{重儿子}s}\)。

于是写成矩阵形式。

\[\begin{bmatrix}f_p\\g_p\\1\end{bmatrix}=\begin{bmatrix}h_p&&h_p\\h_p&1&h_p+u_p\\&&1\end{bmatrix}\begin{bmatrix}f_{\text{重儿子}s}\\g_{\text{重儿子}s}\\1\end{bmatrix} \]

直接上全局平衡二叉树维护就好了。

值得注意的是，在链顶轻儿子信息传递时，\(f_p\) 的维护不能直接乘除，否则可能除零。正确的做法是维护有几个零，以及其余数的乘积。

以下是经过精细卡常的代码。然而还是跑得很慢。

Code 
#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
const uint Mod=10007;
typedef std::vector<uint>modvec;
const uint M=128;
inline uint chg(uint a){return a>=Mod?a-Mod:a;}
voi FWT(modvec&A,bol op){
    for(uint i=1;i<M;i<<=1)for(uint j=0;j<M;j++)if(j&i){uint u=A[i^j],t=A[j];A[i^j]=chg(u+t),A[j]=chg(Mod+u-t);}
    if(op){
        uint w=power(M,Mod-2,Mod);
        for(uint i=0;i<M;i++)(A[i]*=w)%=Mod;
    }
}
typedef std::pair<uint,uint>num;
uint get(num v){return v.second?0:v.first;}
voi insert(num&v,uint w){if(!w)v.second++;else(v.first*=w)%=Mod;}
uint Inv[200005];
voi erase(num&v,uint w){if(!w)v.second--;else(v.first*=Inv[w])%=Mod;}
typedef std::vector<num>numvec;
voi insert(numvec&v,modvec w){for(uint i=0;i<M;i++)insert(v[i],w[i]);}
voi erase(numvec&v,modvec w){for(uint i=0;i<M;i++)erase(v[i],w[i]);}
const modvec zero(M),one(M,1);
struct Mat{
    modvec A00,A02,A10,A12;
    Mat(){A00=A02=A10=A12=zero;}
    friend Mat operator*(Mat a,Mat b){
        Mat ans;
        for(uint i=0;i<M;i++)
            ans.A00[i]=a.A00[i]*b.A00[i]%Mod,
            ans.A02[i]=(a.A00[i]*b.A02[i]+a.A02[i])%Mod,
            ans.A10[i]=(a.A10[i]*b.A00[i]+b.A10[i])%Mod,
            ans.A12[i]=(a.A10[i]*b.A02[i]+b.A12[i]+a.A12[i])%Mod;
        return ans;
    }
};
uint Fath[30005],Son[2][30005];
std::vector<uint>Way[30005];
uint Siz[30005],Heavy[30005],Siz2[30005];
voi dfs(uint p,uint f){
    Siz[p]=1,Fath[p]=f,Heavy[p]=-1;
    for(auto s:Way[p])if(s!=f){dfs(s,p),Siz[p]+=Siz[s];if(!~Heavy[p]||Siz[s]>Siz[Heavy[p]])Heavy[p]=s;}
    Siz2[p]=Siz[p];if(~Heavy[p])Siz2[p]-=Siz[Heavy[p]];
}
numvec H[30005];modvec U[30005],V[30005];
Mat W[30005];
voi pushup(uint p){
    for(uint i=0;i<M;i++)
        W[p].A12[i]=chg(U[p][i]+(W[p].A00[i]=W[p].A02[i]=W[p].A10[i]=get(H[p][i])));
    if(~Son[0][p])W[p]=W[Son[0][p]]*W[p];
    if(~Son[1][p])W[p]=W[p]*W[Son[1][p]];
}
uint build(uint l,uint r,std::vector<uint>&Ps){
    if(l>=r)return-1;
    uint siz=0,w=-1,wp=l;
    for(uint i=l;i<r;i++)siz+=Siz2[Ps[i]];
    for(uint i=l,s=0;i<r;i++){
        uint a=std::max(s,siz-s-Siz2[Ps[i]]);
        if(_min(w,a))wp=i;
        s+=Siz2[Ps[i]];
    }
    if(~(Son[0][Ps[wp]]=build(l,wp,Ps)))Fath[Son[0][Ps[wp]]]=Ps[wp];
    if(~(Son[1][Ps[wp]]=build(wp+1,r,Ps)))Fath[Son[1][Ps[wp]]]=Ps[wp];
    pushup(Ps[wp]);return Ps[wp];
}
uint build(uint p){
    std::vector<uint>A;while(~p)A.push_back(p),p=Heavy[p];
    for(auto p:A)for(auto s:Way[p])if(s!=Fath[p]&&s!=Heavy[p]){
        uint a=build(s);Fath[a]=p;
        for(uint i=0;i<M;i++)insert(H[p][i],chg(W[a].A02[i]+1)),U[p][i]=chg(U[p][i]+W[a].A12[i]);
    }
    return build(0,A.size(),A);
}
voi remove(uint p){
    std::vector<uint>A;
    while(~p){
        if(~Fath[p]&&p!=Son[0][Fath[p]]&&p!=Son[1][Fath[p]])for(uint i=0;i<M;i++)
            erase(H[Fath[p]][i],chg(W[p].A02[i]+1)),U[Fath[p]][i]=chg(U[Fath[p]][i]+Mod-W[p].A12[i]);
        p=Fath[p];
    }
}
voi update(uint p){
    while(~p){
        pushup(p);
        if(~Fath[p]&&p!=Son[0][Fath[p]]&&p!=Son[1][Fath[p]])for(uint i=0;i<M;i++)
            insert(H[Fath[p]][i],chg(W[p].A02[i]+1)),U[Fath[p]][i]=chg(U[Fath[p]][i]+W[p].A12[i]);
        p=Fath[p];
    }
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
#endif
    Inv[1]=1;for(uint i=2;i<Mod;i++)Inv[i]=Inv[Mod%i]*(Mod-Mod/i)%Mod;
    uint n,q;scanf("%u%*u",&n);
    for(uint i=0,v;i<n;i++){
        scanf("%u",&v);V[i]=U[i]=zero;V[i][v]=1,FWT(V[i],0);
        H[i].resize(M,{1,0}),insert(H[i],V[i]),Son[0][i]=Son[1][i]=-1u;
    }
    for(uint i=1,u,v;i<n;i++)scanf("%u%u",&u,&v),Way[--u].push_back(--v),Way[v].push_back(u);
    dfs(0,-1);uint rot=build(0);
    Fath[rot]=-1;
    scanf("%u",&q);
    while(q--){
        chr C[15];scanf("%s",C);
        if(*C=='Q'){
            uint k;scanf("%u",&k);modvec A=W[rot].A12;FWT(A,1);printf("%u\n",A[k]);
        }else{
            uint p,v;scanf("%u%u",&p,&v),p--;
            remove(p),erase(H[p],V[p]),V[p]=zero;V[p][v]=1,FWT(V[p],0),insert(H[p],V[p]),update(p);
        }
    }
    return 0;
}

标签：Heavy,typedef,return,Siz,Fath,uint,二叉树,平衡,全局
From： https://www.cnblogs.com/myee/p/global-biased-tree.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99