线段树合并，顾名思义就是把两棵线段树合并在一起，将两棵树信息相加
复杂度证明：
自己想的证明
设添加入各棵线段树的总点数为 $n$
考虑一条链，长度为 $logm$ ，那么合并这条链的复杂度为 $logm*size[val]$
总复杂度= $logm*size[val_1]+logm*size[val_2]+...+logm*size[val_n]$
因为 $size[val_1] + size[val_2] + ... + size[val_n]$ 等于 $n$
所以复杂度为 $nlogm$

例题

天天爱跑步
https://www.luogu.com.cn/problem/P1600
小 $C$ 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一棵包含 $n$ 个结点和 $n−1$ 条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从 $1$ 到 $n$ 的连续正整数。

现在有 $m$ 个玩家，第 $i$ 个玩家的起点为 $Si$ ，终点为 $Ti$ 。每天打卡任务开始时，所有玩家在第 $0$ 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）

小C想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 j的观察员会选择在第 Wj 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 $W_j$ 秒也正好到达了结点 $j$ 。小 $C$ 想知道每个观察员会观察到多少人？

注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点 $j$ 作为终点的玩家：若他在第 $W_j$ 秒前到达终点，则在结点 $j$ 的观察员不能观察到该玩家；若他正好在第 $W_j$ 秒到达终点，则在结点 $j$ 的观察员可以观察到这个玩家。

$Solution$
考虑如下图
图片说明

也就是说，有两类贡献
在一个观察员的子树中，如果有一条路的起点，那么贡献即为 $dep[s]=dep[x]+w$ 的数量
有终点，那么加入它对应路径的 $dep[s]-2 \times dep[lca]$ 的值，查询 $w-dep[x]$ 的数量
也就是说，我们每一个节点建一棵线段树
对于每一个玩家，我们在它的起点这棵树上加入 $dep[s]$ ，在它的终点加入 $dep[s]-2 \times dep[lca]$
$dfs$ 线段树合并即可
每个观察员的答案即为两类贡献之和
但是这样会出问题， $lca$ 之上的节点会被加入这些起点/终点
所以做一个树上差分
值可能出现负数，所以加一个偏移量 $Code$ :

#include <bits/stdc++.h>
#define ri register int
#define ll long long
#define mid (((l)+(r))>>1)
using namespace std;
const int Maxn=3e5;
int lt[Maxn+5],nt[Maxn*2+5],ed[Maxn*2+5],n,m,cnt;
int dep[Maxn+5],ans[Maxn+5],w[Maxn+5],rt[Maxn+5][2];
int v[Maxn*40+5],ls[Maxn*40+5],rs[Maxn*40+5],node;
int father[Maxn+5][20];
void addedge(int x,int y) {
    ed[++cnt]=y;nt[cnt]=lt[x];lt[x]=cnt;
}
void change(int &p,int l,int r,int k,int d) {
    if(!p)p=++node;
    if(l==r) {
        v[p]+=d;return ;
    }
    if(k<=mid)change(ls[p],l,mid,k,d);
    else change(rs[p],mid+1,r,k,d);
}
int merge(int x,int y,int l,int r) {
    if(!x||!y)return x+y;
    if(l==r) {
        v[x]+=v[y];return x;
    }
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    return x;
}
int query(int p,int l,int r,int k) {
    if(l==r)return v[p];
    if(k<=mid)return query(ls[p],l,mid,k);
    return query(rs[p],mid+1,r,k);
}
void dfs(int u,int fa) {
    dep[u]=dep[fa]+1;father[u][0]=fa;
    int t=ceil(log2(dep[u]));
    for(ri i=1;i<=t;i++)father[u][i]=father[father[u][i-1]][i-1];
    for(ri i=lt[u];i;i=nt[i])
        if(ed[i]!=fa)dfs(ed[i],u);
}
int go_up(int u,int k) {
    int t=ceil(log2(dep[u]));
    for(ri i=0;i<=t;i++)
        if(k>>i&1)u=father[u][i];
    return u;
}
int lca(int x,int y) {
    if(dep[x]<dep[y])swap(x,y);
    x=go_up(x,dep[x]-dep[y]);
    if(x==y)return x;
    int t=ceil(log2(dep[x]));
    for(ri i=t;i>=0;i--)
        if(father[x][i]!=father[y][i]) {
            x=father[x][i];
            y=father[y][i];
        }
    return father[x][0];
}
void solve(int u,int fa) {
    for(ri i=lt[u];i;i=nt[i]) {
        int v=ed[i];
        if(v!=fa) {
            solve(v,u);
            merge(rt[u][0],rt[v][0],1,n);
            merge(rt[u][1],rt[v][1],0,2*n);
        }
    }
    if(w[u]+dep[u]<=n)ans[u]+=query(rt[u][0],1,n,w[u]+dep[u]);
    ans[u]+=query(rt[u][1],0,2*n,w[u]-dep[u]+n);
}
int main() {
    scanf("%d%d",&n,&m);
    for(ri i=1;i<n;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    dfs(1,0);
    for(ri i=1;i<=n;i++)scanf("%d",&w[i]),rt[i][0]=++node,rt[i][1]=++node;
    for(ri i=1;i<=m;i++) {
        int s,t;
        scanf("%d%d",&s,&t);
        int o=lca(s,t);
        change(rt[s][0],1,n,dep[s],1);
        change(rt[t][1],0,2*n,dep[s]-2*dep[o]+n,1);
        change(rt[o][1],0,2*n,dep[s]-2*dep[o]+n,-1);
        change(rt[father[o][0]][0],1,n,dep[s],-1);
    }
    solve(1,0);
    for(ri i=1;i<=n;i++)printf("%d ",ans[i]);
    return 0;
}

2. $Peaks$
https://www.luogu.com.cn/problem/P4197
在 $Bytemountains$ 有 $N$ 座山峰，每座山峰有他的高度。
有些山峰之间有双向道路相连，共 $M$ 条路径，每条路径有一个困难值，这个值越大表示越难走，
现在有 $Q$ 组询问，每组询问询问从点 $v$ 开始只经过困难值小于等于 $x$ 的路径所能到达的山峰中第 $k$ 高的山峰，如果无解输出 $-1$ 。

$Solution$
$1$ 离线
将边按边权从小到大排序，将询问按 $x$ 从小到大排序
每次将小于当前困难值的边加入
具体而言，合并两个点，将他们并查集根节点线段树合并
查询第 $K$ 大即可
Code:

#include <bits/stdc++.h>
#define ri register int
#define ll long long
#define mid (((l)+(r))>>1)
using namespace std;
const int Maxn=1e5;
const int Maxm=5e5;
struct Edge {
    int x,y,z;
}e[Maxm+5];
struct Question {
    int u,x,k,id;
}q[Maxm+5];
int n,m,Q;
int ls[Maxn*20+5],rs[Maxn*20+5],v[Maxn*20+5],rt[Maxn+5],node;
int a[Maxn+5],lsh[Maxn+5],org[Maxn+5],father[Maxn+5],ans[Maxm+5];
bool cmp(Edge a,Edge b) {
    return a.z<b.z;
}
bool cmp2(Question a,Question b) {
    return a.x<b.x;
}
int getfather(int v) {
    return father[v]==v?v:father[v]=getfather(father[v]);
}
void update(int p) {
    v[p]=v[ls[p]]+v[rs[p]];
}
void change(int &p,int l,int r,int k,int d) {
    if(!p)p=++node;
    if(l==r) {
        v[p]+=d;return ;
    }
    if(k<=mid)change(ls[p],l,mid,k,d);
    else change(rs[p],mid+1,r,k,d);
    update(p);
}
int merge(int x,int y,int l,int r) {
    if(!x||!y)return x+y;
    if(l==r) {
        v[x]+=v[y];return x;
    }
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    update(x);
    return x;
}
int query(int p,int l,int r,int k) {
    if(l==r)return l;
    if(k<=v[rs[p]])return query(rs[p],mid+1,r,k);
    return query(ls[p],l,mid,k-v[rs[p]]);
}
int main() {
    scanf("%d%d%d",&n,&m,&Q);
    for(ri i=1;i<=n;i++)scanf("%d",&a[i]),lsh[i]=a[i],father[i]=i;
    sort(lsh+1,lsh+n+1);
    int cnt=unique(lsh+1,lsh+n+1)-lsh-1;
    for(ri i=1;i<=n;i++) {
        int t=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
        org[t]=a[i];
        change(rt[i],1,n,t,1);
    }
    for(ri i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
    for(ri i=1;i<=Q;i++)scanf("%d%d%d",&q[i].u,&q[i].x,&q[i].k),q[i].id=i;
    sort(e+1,e+m+1,cmp);sort(q+1,q+Q+1,cmp2);
    int now=1;
    for(ri i=1;i<=Q;i++) {
        while(e[now].z<=q[i].x&&now<=m) {
            int fx=getfather(e[now].x),fy=getfather(e[now].y);
            if(fx!=fy) {
                merge(rt[fx],rt[fy],1,n);father[fy]=fx;
            }
            ++now;
        }
        int x=getfather(q[i].u);
        if(v[rt[x]]<q[i].k)ans[q[i].id]=-1;
        else ans[q[i].id]=org[query(rt[x],1,n,q[i].k)]; 
    }
    for(ri i=1;i<=Q;i++)printf("%d\n",ans[i]); 
    return 0;
}

2 在线
建出重构树
因为重构树点权从下到上单调不减，所以可以树上倍增，找到最高的那个点满足点权小于 $x$
所以只经过困难之不超过 $x$ 的边能到的点即是这个点子树中的实点
那么先 $dfs$ 合并出每个点的线段树
到时候查询即可
注意合并的时候可持久化
Code:

#include <bits/stdc++.h>
#define ri register int
#define ll long long
#define mid (((l)+(r))>>1)
using namespace std;
const int Maxn=1e5;
const int Maxm=5e5;
const int Inf=1e9+1;
struct Edge {
    int x,y,z;
}e[Maxm+5];
int father[Maxn*2+5][20],fa[Maxn*2+5],n,m,q,now;
int ls[Maxn*50+5],rs[Maxn*50+5],v[Maxn*50+5],rt[2*Maxn+5],node;
int a[Maxn+5],val[2*Maxn+5],lsh[Maxn+5];
int lt[Maxn*2+5],nt[Maxn*2+5],ed[Maxn*2+5],dep[2*Maxn+5],cnt;
bool cmp(Edge a,Edge b) {
    return a.z<b.z;
}
void addedge(int x,int y) {
    ed[++cnt]=y;nt[cnt]=lt[x];lt[x]=cnt;
}
int getfather(int v) {
    return fa[v]==v?v:fa[v]=getfather(fa[v]);
}
void kruscal() {
    sort(e+1,e+m+1,cmp);
    for(ri i=1;i<=2*n-1;i++)fa[i]=i;
    now=n;
    for(ri i=1;i<=m;i++) {
        int x=getfather(e[i].x),y=getfather(e[i].y);
        if(x!=y) {
            ++now;
            addedge(now,x);
            addedge(now,y);
            fa[x]=now,fa[y]=now;
            val[now]=e[i].z;
        }
    }
}
void update(int p) {
    v[p]=v[ls[p]]+v[rs[p]];
}
void change(int &p,int l,int r,int k,int d) {
    if(!p)p=++node;
    if(l==r) {
        v[p]+=d;return ;
    }
    if(k<=mid)change(ls[p],l,mid,k,d);
    else change(rs[p],mid+1,r,k,d);
    update(p);
}
int merge(int x,int y,int l,int r) {
    if(!x||!y)return x+y;
    int z=++node;
    if(l==r) {
        v[z]=v[x]+v[y];return z;
    }
    ls[z]=merge(ls[x],ls[y],l,mid);
    rs[z]=merge(rs[x],rs[y],mid+1,r);
    update(z);
    return z;
}
int query(int p,int l,int r,int k) {
    if(l==r)return l;
    if(k<=v[rs[p]])return query(rs[p],mid+1,r,k);
    return query(ls[p],l,mid,k-v[rs[p]]);
}
void dfs(int u,int fa) {
    dep[u]=dep[fa]+1;
    father[u][0]=fa;
    int t=ceil(log2(dep[u]));
    for(ri i=1;i<=t;i++)father[u][i]=father[father[u][i-1]][i-1];    
    for(ri i=lt[u];i;i=nt[i]) {
        int v=ed[i];
        dfs(v,u);
        rt[u]=merge(rt[u],rt[v],1,n);
    }
}
int main() {
    scanf("%d%d%d",&n,&m,&q);
    for(ri i=1;i<=n;i++)scanf("%d",&a[i]),lsh[i]=a[i];
    sort(lsh+1,lsh+n+1);
    int cnt=unique(lsh+1,lsh+n+1)-lsh-1;
    for(ri i=1;i<=n;i++) {
        a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
        change(rt[i],1,n,a[i],1);
    }
    for(ri i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
    kruscal();
    for(ri i=1;i<=now;i++)
        if(fa[i]==i)dfs(i,0);
    val[0]=Inf;
    while(q--) {
        int u,x,k;
        scanf("%d%d%d",&u,&x,&k);
        int t=ceil(log2(dep[u]));
        for(ri i=t;i>=0;i--)
            if(val[father[u][i]]<=x)u=father[u][i];
        if(v[rt[u]]<k)printf("-1\n");
        else printf("%d\n",lsh[query(rt[u],1,n,k)]);
    }
    return 0;
}

3 $HNOI2009$ 梦幻布丁
https://www.luogu.com.cn/problem/P3201 $N$ 个布丁摆成一行,进行 $M$ 次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为 $1,2,2,1$ 的四个布丁一共有3段颜色.

$Solution$
显然是对每一个颜色建一棵线段树，记录这个颜色的位置
我们考虑当前修改对答案的影响，查询时直接输出ans即可
那么这个修改是一个明显的线段树合并，我们将两棵线段树位置信息合并即可
具体而言，我们在每个节点记录这一区间有多少段这个颜色，以及左右端点是否被涂掉
合并时 $v[p]=v[ls(p)]+v[rs(p)]-(rt[ls(p)]$ $and$ $lt[rs(p)])$ ，即中间这一段可能算重
那么问题变成了，如何将被修改的颜色线段树清零
这好办，我们把它的根节点砍成“光杆司令”，清空 $v[]$ 值，和左右儿子
修改答案时， $ans$ 先减去两个颜色的段数，在加上合并后颜色的段数即可
Code:

#include <bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int Maxn=1e5;
const int Maxm=1e6;
int v[Maxm*18+5],lt[Maxm*18+5],rt[Maxm*18+5],ls[Maxm*18+5],rs[Maxm*18+5],node;
int a[Maxn+5],rot[Maxm+5],n,m;
#define mid (((l)+(r))>>1)
void update(int p) {
    v[p]=v[ls[p]]+v[rs[p]]-(rt[ls[p]]&lt[rs[p]]);
    lt[p]=lt[ls[p]],rt[p]=rt[rs[p]];
}
void change(int &p,int l,int r,int k) {
    if(!p)p=++node;
    if(l==r) {
        v[p]=1;lt[p]=rt[p]=1;return ;
    }
    if(k<=mid)change(ls[p],l,mid,k);
    else change(rs[p],mid+1,r,k);
    update(p);
}
int merge(int x,int y,int l,int r) {
    if(!x||!y)return x+y;
    if(l==r) {
        v[x]|=v[y],lt[x]|=lt[y],rt[x]|=rt[y];
        return x;
    }
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    update(x);
    return x;
}
int main() {
    scanf("%d%d",&n,&m);
    for(ri i=1;i<=n;i++)scanf("%d",&a[i]);
    for(ri i=1;i<=Maxm;i++)rot[i]=++node;
    for(ri i=1;i<=n;i++)change(rot[a[i]],1,n,i);
    int ans=0;
    for(ri i=1;i<=n;i++)
        if(a[i]!=a[i-1])++ans;
    for(ri i=1;i<=m;i++) {
        int op,x,y;
        scanf("%d",&op);
        if(op==2)printf("%d\n",ans);
        else {
            scanf("%d%d",&x,&y);
            if(x!=y) {
                swap(x,y);
                ans-=v[rot[x]]+v[rot[y]];
                merge(rot[x],rot[y],1,n);
                ans+=v[rot[x]];
                ls[rot[y]]=0,rs[rot[y]]=0,v[rot[y]]=0;
            }
        }
    }
    return 0;
}

[学习笔记]线段树合并

例题