投稿
  1. 高性能架构探索首页
  2. C/C++

线段树合并&分裂

admin • • C/C++ • 阅读 168

线段树合并&分裂

线段树合并

所谓线段树合并就是将两个线段树合并成一颗线段树的算法

il int merge(int rt1,int rt2,int l,int r){
    if(!(rt1*rt2)) return rt1+rt2;
    if(l==r) return t[rt1].sum+=t[rt2].sum,rt1;
    t[rt1].ls=merge(t[rt1].ls,t[rt2].ls,l,mid);
    t[rt1].rs=merge(t[rt1].rs,t[rt2].rs,mid+1,r);
    return pushup(rt1),rt1;
}
AC·code 
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;

namespace Q{
    il int rd(){
        ri int x=0;ri bool f=0;ri char c=getchar();
        while(!isdigit(c)) f|=(c=='-'),c=getchar();
        while(isdigit(c))x=x*10+(c^48),c=getchar();
        return f?-x:x;
    }
    il void wt(int x){
        if(x<0) x=-x,putchar('-');
        if(x>=10) wt(x/10);
        return putchar(x%10+48),void();
    }
} 

cs int N=1e5;

int n,m;

namespace edge{
    int h[N+1];
    struct qwq{
        int v,nxt;
    }e[N<<1];
    il void add(cs int u,cs int v,cs int i){
        e[i*2-1]={v,h[u]},h[u]=i*2-1;
        e[i<<1]={u,h[v]},h[v]=i<<1;
    }
} 

namespace LCA{   
    int f[N+1][20],dep[N+1];
    il void dfs(int u){
        dep[u]=dep[f[u][0]]+1;
        for(ri int i=edge::h[u];i;i=edge::e[i].nxt){
            if(edge::e[i].v!=f[u][0]){
                f[edge::e[i].v][0]=u;
                for(ri int l=1;l<20;++l){
                    f[edge::e[i].v][l]=f[f[edge::e[i].v][l-1]][l-1];
                }
                dfs(edge::e[i].v);
            }
        }
        return;
    }
    il int lca(int u,int v){
        if(dep[u]<dep[v]) swap(u,v);
        for(ri int l=19;~l;--l){
            if(dep[f[u][l]]>=dep[v]) u=f[u][l];
        }
        if(u==v) return u;
        for(ri int l=19;~l;--l){
            if(f[u][l]!=f[v][l]){
                u=f[u][l],v=f[v][l];
            }
        }
        return f[u][0];
    }
} 

namespace Tree{
    struct tree{
        int ls,rs,sum,num;
    }t[N*80];
    il void pushup(cs int rt){
        if(!t[rt].ls){
            t[rt].sum=t[t[rt].rs].sum;
            t[rt].num=t[t[rt].rs].num;
        }
        else if(!t[rt].rs){
            t[rt].sum=t[t[rt].ls].sum;
            t[rt].num=t[t[rt].ls].num;
        }
        else if(t[t[rt].ls].sum>=t[t[rt].rs].sum){
            t[rt].sum=t[t[rt].ls].sum;
            t[rt].num=t[t[rt].ls].num;
        } 
        else{
            t[rt].sum=t[t[rt].rs].sum;
            t[rt].num=t[t[rt].rs].num;
        } 
        return;
    }
    int cnt;
    #define mid ((l+r)>>1)
    il void add(int &rt,int l,int r,int knd,int val){
        if(!rt) rt=++cnt;
        if(l==r) return t[rt].sum+=val,t[rt].num=knd,void();
        if(knd<=mid) add(t[rt].ls,l,mid,knd,val);
        else add(t[rt].rs,mid+1,r,knd,val);
        return pushup(rt);
    }
    il int merge(int rt1,int rt2,int l,int r){
        if(!(rt1*rt2)) return rt1+rt2;
        if(l==r) return t[rt1].sum+=t[rt2].sum,rt1;
        t[rt1].ls=merge(t[rt1].ls,t[rt2].ls,l,mid);
        t[rt1].rs=merge(t[rt1].rs,t[rt2].rs,mid+1,r);
        return pushup(rt1),rt1;
    }
    int rot[N+1],as[N+1];
    il void sol(int u){
        for(ri int i=edge::h[u],v;i;i=edge::e[i].nxt){
            if((v=edge::e[i].v)!=LCA::f[u][0]){
                sol(v),rot[u]=Tree::merge(rot[u],rot[v],1,N);
            }
        }
        as[u]=Tree::t[rot[u]].num;
        if(!Tree::t[rot[u]].sum) as[u]=0;
        return;
    }
} 

signed main(){
    n=Q::rd(),m=Q::rd();
    for(ri int i=1;i<n;++i){
        edge::add(Q::rd(),Q::rd(),i);
    }
    LCA::dfs(1);
    for(ri int i=1,u,v,num,l;i<=m;++i){
        u=Q::rd(),v=Q::rd(),num=Q::rd();
        Tree::add(Tree::rot[u],1,N,num,1);
        Tree::add(Tree::rot[v],1,N,num,1);
        l=LCA::lca(u,v),Tree::add(Tree::rot[l],1,N,num,-1);//N不是n
        Tree::add(Tree::rot[LCA::f[l][0]],1,N,num,-1);
        //是rot[u]，不是u，每个节点建一颗树!!!
    }
    Tree::sol(1);
    for(ri int i=1;i<=n;++i){
        Q::wt(Tree::as[i]),putchar('\n');
    }
    return 0;
}

线段树分裂

分裂的主要思路在于动态开点和值的转移，将原值附在新树上同时清空原点（不是删除）。

il int split(int pre,int l,int r,int ql,int qr){
    ri int rt=++id;
    if(ql<=l&&r<=qr) t[rt]=t[pre],t[pre]=(tr){0,0,0};
    else{
        if(mid>=qr) ls=split(t[pre].Ls,l,mid,ql,qr);
        else if(mid<ql) rs=split(t[pre].Rs,mid+1,r,ql,qr);            
        else{//
            ls=split(t[pre].Ls,l,mid,ql,mid);
            rs=split(t[pre].Rs,mid+1,r,mid+1,qr);
        }
        pushup(rt),pushup(pre);
    }
    return rt;
}
AC·code 
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define int long long
using namespace std;

namespace Q{
    il int rd(){
        ri int x=0;ri bool f=0;ri char c=getchar();
        while(!isdigit(c)) f|=(c==45),c=getchar();
        while(isdigit(c)) x=x*10+(c^48),c=getchar();
        return f?-x:x;
    }
    short a[30],tl;
    il void wt(int x){
        if(x<0) x=-x,putchar(45);
        do a[++tl]=x%10,x/=10; while(x);
        while(tl) putchar(a[tl--]|48);
        return putchar(10),void();
    }
} using namespace Q;

cs int N=2e5+1;

namespace tree{
    #define ls t[rt].Ls
    #define rs t[rt].Rs
    #define mid ((l+r)>>1)
    int id,rot[N],tot;
    struct tr{
        int sum,Ls,Rs;
    }t[N<<5];    
    il void pushup(int rt){
        t[rt].sum=t[ls].sum+t[rs].sum;
        return;
    }
    il int build(int l,int r){
        ri int rt=++id;
        if(l==r) t[rt].sum=rd();
        else{
            ls=build(l,mid);
            rs=build(mid+1,r);
            pushup(rt);
        }        
        return rt;
    }    
    il int split(int pre,int l,int r,int ql,int qr){
        ri int rt=++id;
        if(ql<=l&&r<=qr) t[rt]=t[pre],t[pre]=(tr){0,0,0};
        else{
            if(mid>=qr) ls=split(t[pre].Ls,l,mid,ql,qr);
            else if(mid<ql) rs=split(t[pre].Rs,mid+1,r,ql,qr);            
            else{//
                ls=split(t[pre].Ls,l,mid,ql,mid);
                rs=split(t[pre].Rs,mid+1,r,mid+1,qr);
            }
            pushup(rt),pushup(pre);
        }
        return rt;
    }
    il int merge(int rt,int pre){
        if(!(rt*pre)) return rt+pre;
        t[rt].sum+=t[pre].sum;
        ls=merge(ls,t[pre].Ls);
        rs=merge(rs,t[pre].Rs);
        return rt;
    }
    il void add(int &rt,int l,int r,int pos,int k){
        if(!rt) rt=++id; t[rt].sum+=k;
        if(l^r){
            if(mid>=pos) add(ls,l,mid,pos,k);
            else add(rs,mid+1,r,pos,k);
        } 
        return;
    }
    il int ask(int rt,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return t[rt].sum;
        ri int as=0;
        if(mid>=ql) as+=ask(ls,l,mid,ql,qr); 
        if(mid<qr) as+=ask(rs,mid+1,r,ql,qr);
        return as;
    }
    il int kth(int rt,int l,int r,int k){
        if(l==r) return l;
        if(t[ls].sum>=k) return kth(ls,l,mid,k);
        else return kth(rs,mid+1,r,k-t[ls].sum);
    }
    il int siz(int p,int n){
        return ask(rot[p],1,n,1,n);
    }
    #undef ls
    #undef rs
    #undef mid
} using namespace tree;

signed main(){
    ri int n=rd(),m=rd();rot[++tot]=build(1,n);
    for(ri int i=1,op,p,x,y;i<=m;++i){
        op=rd(),p=rd(),x=rd();
        if(op==0) y=rd(),rot[++tot]=split(rot[p],1,n,x,y);
        if(op==1) rot[p]=merge(rot[p],rot[x]);
        if(op==2) y=rd(),add(rot[p],1,n,y,x);
        if(op==3) y=rd(),wt(ask(rot[p],1,n,x,y));
        if(op==4) wt(siz(p,n)<x?-1:kth(rot[p],1,n,x));
    }    
    return 0;
}

原文链接: https://www.cnblogs.com/windymoon/p/17124371.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

    线段树合并&分裂

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/318404

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月16日 下午3:04
下一篇 2023年2月17日 上午9:32

相关推荐