线段树合并，顾名思义，就是将两个线段树合并在一起（这里的线段树大多是动态开点的权值线段树）
首先线段树合并就是把一大堆权值线段树合并起来的算法
实现流程就是，同时递归的遍历两个要合并的线段树 \(A,B\)，有如下几种情况：
1.现在在合并 区间 \(2,4\) 对应的节点, \(A\) 有而 \(B\) 没有这个节点，那么我们直接返回 \(A\) 的这个节点
2.现在在合并区间 \(2,2\) 对应的节点 因为是叶子节点，所以我们直接将 这这两棵树的这个节点的值相加，返回
3.那不是叶子节点两棵树都有的节点呢？将这两颗树的这个节点的左右儿子分别合并即可
尽管复杂度看起来并不是非常科学，但是确是非常优秀的 \(O(nlogn)\)
主要的写法两种
int merge(int x,int y,int l,int r)//将 y 合并到 x 上（注意，这种合并后 y 不可以再与别的线段树合并）
{
if(!x||!y)//有一边节点为空
{
return x+y;//返回另一边的
}
if(l==r)//是叶子节点
{
sgt[x].sum+=sgt[y].sum;//加起来
return x;//返回
}
int mid=(l+r)>>1;
sgt[x].ls=merge(sgt[x].ls,sgt[y].ls,l,mid);//左右儿子节点分别合并
sgt[x].rs=merge(sgt[x].rs,sgt[y].rs,mid+1,r);
update(x);//更新这个节点
return x;
}
把 \(y\) 合并到 \(x\) 上
但是我们这样直接把 \(y\) 合并过来的话，因为 \(x\) 共用了 \(y\) 的节点，以后 \(y\) 与别的树合并时就可能影响到 \(x\)
所以这种写法中的 \(y\) 树在之后就不能与别的树合并
我们也可以像主席树那样，合并不在原来的树上而是新开节点，
缺点就是特别特别炸空间
总的代码:P4556 [Vani有约会] 雨天的尾巴-模板-线段树合并
#include <bits/stdc++.h>
using namespace std;
struct node //线段树
{
int l, r;
int ls, rs;
int sum;
int typ;
};
node sgt[1000000];
struct tree //树
{
int dfn;
vector<int> son;
int deep;
};
int n,m;
tree tr[100005];
int root[100005], idx; //树根记录
int fa[100005][20];
int dfn;
int dfn_[100005];//DFN序
void build_t(int x, int f)//倍增
{
tr[x].deep = tr[f].deep + 1;
fa[x][0] = f;
tr[x].dfn=++dfn;
dfn_[dfn]=x;
for (int i = 1; i <= 18; i++)
{
fa[x][i] = fa[fa[x][i - 1]][i - 1];
}
for (int to : tr[x].son)
{
if (to != f)
{
build_t(to, x);
}
}
}
int get_lca(int x, int y)
{
if (tr[x].deep < tr[y].deep)
{
swap(x, y);
}
for (int i = 18; i >= 0; i--)
{
if (tr[fa[x][i]].deep >= tr[y].deep)
{
x = fa[x][i];
}
}
if (x == y)
{
return y;
}
for (int i = 18; i >= 0; i--)
{
if (fa[x][i] != fa[y][i])
{
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
// sgt启动！
void update(int p) //上传 权值线段树
{
if (sgt[sgt[p].ls].sum >= sgt[sgt[p].rs].sum) //取左右子树中最大的sum
{
sgt[p].sum = sgt[sgt[p].ls].sum;
sgt[p].typ = sgt[sgt[p].ls].typ;
}
else
{
sgt[p].sum = sgt[sgt[p].rs].sum;
sgt[p].typ = sgt[sgt[p].rs].typ;
}
}
void change(int &p,int l,int r,int kind_,int delt)//点修
{
if(!p)
{
p=++idx;
}
if(l==r)
{
sgt[p].sum+=delt;
sgt[p].typ=kind_;
return;
}
int mid=(l+r)>>1;
if(kind_<=mid)
{
change(sgt[p].ls,l,mid,kind_,delt);
}
else
{
change(sgt[p].rs,mid+1,r,kind_,delt);
}
update(p);
}
int merge(int x,int y,int l,int r)//线段树合并
{
if(!x||!y)
{
return x+y;
}
if(l==r)
{
sgt[x].sum+=sgt[y].sum;
}
int mid=(l+r)>>1;
sgt[x].ls=merge(sgt[x].ls,sgt[y].ls,l,mid);
sgt[x].rs=merge(sgt[x].rs,sgt[y].rs,mid+1,r);
update(x);
return x;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
int a,b,c;
for(int ww=1;ww<n;ww++)
{
cin>>a>>b;
tr[a].son.push_back(b);
tr[b].son.push_back(a);
}
for(int ww=1;ww<=m;ww++)
{
cin>>a>>b>>c;
change(root[a],1,100001,c,1);//树上差分
change(root[b],1,100001,c,1);
int lca_=get_lca(a,b);
change(root[lca_],1,100001,c,-1);
change(root[fa[lca_][0]],1,100001,c,-1);
}
for(int ww=n;ww>=1;ww--)//按dfn序依次向父节点合并
{
int now_=dfn_[ww];
root[fa[now_][0]]=merge(root[fa[now_][0]],root[now_],1,100001);
}
for(int ww=1;ww<=n;ww++)
{
cout<<sgt[root[ww]].typ<<"\n";
}
return 0;
}