跳转至

线段树合并

例题 #1

首先村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\) 次发放，每次选择两个房屋 \((x, y)\)，然后对于 \(x\) 到 \(y\) 的路径上（含 \(x\) 和 \(y\)）每座房子里发放一袋 \(z\) 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

初步思路

  • 对于每一种粮食我们都建一颗线段树。最后我们把这些线段树合并，按最大值的方式。

  • 我们在每个简单维护z的数组记录每种粮食的数量

  • 我们用线段树套线段树，在每个节点（区间加线段树）上维护最大值线段树。

  • 对于维护链上的加减，要映射要区间中，我们使用树链剖分。

很明显这些思路空间明显不够。

但是方法3貌似是时间复杂度正确的一种方法。方法4也是可以用的。

线段树合并

实际上，我们可以维护 n个权值线段树。并且最后，因为这n个线段树是**相似的**，所以我们可以通过线段树合并来维护答案。

如果说我们要合并两颗线段树，其实还是很简单的。我们用一个指针x同时访问\(tr1_x,tr2_x\)。这里我们将tr2合并到tr1上。

  • 如果两个节点都有值，那么递归合并。

  • 如果tr1有而tr2无，直接return（因为假设当前某棵线段树上的当前节点没有值，那么这个节点的子树也一定没有值，合并就没有意义了。）

  • 如果tr2有而tr1无，直接复制过来即可。

注意同一个指针指的是两个指针指向两个线段树中的相同节点，相同节点定义为代表的区间相同。下面是动态开点线段树的合并，因此我们需要两个指针。

int  merge(int x,int y int l,int r){
    if(!x||!y)return x+y;//一个空，返回另一个
    if(l==r){
        tr[x].sum+=tr[y].sum;
        return x;
    }

    int mid=l+r>>1;
    tr[x].l=merge(tr[x].l,tr[y].l,l,mid);
    tr[x].r=merge(tr[x].r,tr[y].r,mid+1,r);
    pushup(x);
    return x;
}

线段树合并——P4556 雨天的尾巴_哔哩哔哩_bilibili

例题思路

我们在每一个节点都建立一颗线段树，线段树维护每一种救济粮的数量。但是这个做法不对，我们后面会讲。

对于修改路径上的值，我们采用**差分**即可。注意这里是点差分，即我们在u,v处+1，lca处-1，lca的祖先处也-1。

欸？我们为什么需要树上差分呢？都每个节点开线段树了怎么差分呢？

其实想一想就知道我们是不可能每个节点都开线段树的，那样会爆空间。实际上，假设我们在u-v路径上发放z，那么我们就在u,v处动态开点线段树上把z+1，在lca和lca的祖先的线段树上-1，这样我们就不需要维护很多棵线段树了。

最后我们在统计答案时按前缀和方法还原树，这样就需要我们**合并线段树**了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ps second
#define pf first


#define rd read()
int read()
{
    int xx=0,ff=1;
    char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') ff=-1;c=getchar();}
    while(c>='0'&&c<='9') xx=xx*10+(c-'0'),c=getchar();
    return xx*ff;
}
void write(int out)
{
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}


const int N=2e5+5;
const int M=5e5+5;
const int INF=1e9+5;
const int base=23;
const int MOD=19260817;

int n,m,ans[N];
vector<int> e[N];
int fa[N][20],dep[N];
int rt[N],tot;
int ls[N*50],rs[N*50],sum[N*50],typ[N*50];
//sum:某种救济粮的数量
//typ:救济粮的类型

namespace LCA{

    void dfs(int x,int f){ 
        dep[x]=dep[f]+1; fa[x][0]=f;
        for(int i=1; i<=18; i++)
            fa[x][i]=fa[fa[x][i-1]][i-1]; 
        for(int v:e[x])
            if(v!=f) dfs(v,x);
        }
        int lca(int x,int v){ //求lca
        if(dep[x]<dep[v]) swap(x,v);
        for(int i=18; ~i; i--)
            if(dep[fa[x][i]]>=dep[v])x=fa[x][i];
        if(x==v) return v;
        for(int i=18; ~i; i--)
            if(fa[x][i]!=fa[v][i])x=fa[x][i],v=fa[v][i];
        return fa[x][0];
    }

}

using namespace LCA;

void pushup(int x){ //上传
    if(sum[ls[x]]>=sum[rs[x]])sum[x]=sum[ls[x]], typ[x]=typ[ls[x]];
    else sum[x]=sum[rs[x]], typ[x]=typ[rs[x]];
}
    void change(int &x,int l,int r,int p,int k){ 
    if(!x) x=++tot; //动态开点
    if(l==r){sum[x]+=k; typ[x]=p; return;}
    int mid=l+r>>1;
    if(p<=mid) change(ls[x],l,mid,p,k);
    else change(rs[x],mid+1,r,p,k);
    pushup(x);
}
int merge(int x,int v,int l,int r){ //合并
    if(!x||!v)return x+v;//一个空,返回另一个
    if(l==r){sum[x]+=sum[v]; return x;}
    int mid=l+r>>1;
    ls[x]=merge(ls[x],ls[v],l,mid);
    rs[x]=merge(rs[x],rs[v],mid+1,r);
    pushup(x);
    return x;
}
void dfs2(int x,int f){ //递归合并
    for(int v:e[x]){
        if(v==f) continue;
        dfs2(v,x);
        rt[x]=merge(rt[x],rt[v],1,N);
    }
    ans[x]=sum[rt[x]]?typ[rt[x]]:0;
}
signed main(){
    n=rd,m=rd;
    for(int i=1; i<n; i++){
        int x=rd,v=rd;
        e[x].push_back(v);
        e[v].push_back(x);
    }
    dfs(1,0); 
    for(int i=1; i<=m; i++){ //差分
        int x=rd,v=rd,z=rd;
        change(rt[x],1,N,z,1);
        change(rt[v],1,N,z,1);
        int t=lca(x,v);
        change(rt[t],1,N,z,-1);
        change(rt[fa[t][0]],1,N,z,-1);
    }
    dfs2(1,0); //递归合并
    for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
}