线段树合并
by 0htoAi 于 2021.7.31
早年作品不保证可靠。
1.关于线段树合并：
多棵大小相同的线段树，对应节点相加组成的新线段树。
新线段树既可以单独成树，也可以附在一棵参与合并的旧线段树上。
附1：大多数时候线段树合并都是权值线段树合并。
附2：大多数时候合并都是附在一棵参与合并的线段树上，节约空间。
合并代码如下，表示把线段树2的u2号节点合并到线段树1的u1号节点。
点击查看代码
int Merge(int u1,int u2,int x,int y)
{
if(!u1||!u2)return u1+u2;
if(x==y)
{
tr[u1].val+=tr[u2].val;
return u1;
}
int mid=x+y>>1;
tr[u1].ls=Merge(tr[u1].ls,tr[u2].ls,x,mid);
tr[u1].rs=Merge(tr[u1].rs,tr[u2].rs,mid+1,y);
tr[u1].val=tr[tr[u1].ls].val+tr[tr[u1].rs].val;
tr[u2].val=0;
return u1;
}
合并效果图：
2.关于习题
1.[USACO17JAN]Promotion Counting P
题意：
找一棵树上每个节点的子树里有多少个比这个节点权值大的节点。
思路：
从下到上递归建权值线段树，每个节点最开始建立的线段树只包含这个点的权值，也就是只有1个叶子节点有值的权值线段树。
递归每找完一个子节点就将子节点的线段树合并到当前节点上。
找完子节点后的当前节点的线段树所包含的就是这个节点子树的所有节点权值。
再查找这棵树的 \(P_u+1\) 到 \(P_{max}\) 的和就行了。
关键代码：
建树：
点击查看代码
void BuildTree(int &u,int x,int y,int z)
{
if(u==0)
u=++tot;
if(x==y)
{
tr[u].x=tr[u].y=x;
tr[u].val=1;
tr[u].ls=tr[u].rs=0;
return;
}
tr[u].x=x;
tr[u].y=y;
int mid=x+y>>1;
if(z>mid)
BuildTree(tr[u].rs,mid+1,y,z);
else
BuildTree(tr[u].ls,x,mid,z);
tr[u].val=tr[tr[u].ls].val+tr[tr[u].rs].val;
}
查询：
点击查看代码
int Query(int &u,int x,int y)
{
if(tr[u].x>=x&&tr[u].y<=y)
return tr[u].val;
if(tr[u].x==tr[u].y)
return tr[u].val;
int Sum=0;
int mid=tr[u].x+tr[u].y>>1;
if(mid>=x&&y>=tr[u].x)
Sum+=Query(tr[u].ls,x,y);
if(mid递归：
点击查看代码
void dfs(int u)
{
if(root[u]==0)
root[u]=++tot;
BuildTree(root[u],1,Maxm,P[u]);
for(int i=elast[u];i;i=e[i].Next)
{
int v=e[i].y;
dfs(v);
root[u]=Merge(root[u],root[v],1,Maxm);
}
Ans[u]=Query(root[u],P[u]+1,Maxm);
}
小结：
线段树合并模板题，没有思维难度，第一次打比较考验码力。
注：此题需要离散化
2.[HNOI2012] 永无乡
题意：
动态找连通块第 \(k\) 小。
思路：
每当遇到连通块，第一时间想到并查集维护连通性。
同样对于每一个岛屿建立权值线段树，最开始只包含这个岛屿的重要度。
每次建桥就将桥两头的岛屿所在的的连通块合并。
对于每次询问进行线段树上二分查找，所以还得记录每个节点所包含权值区间的岛屿个数。
（小细节：对于每个询问，输出的是岛屿编号，而不是岛屿重要度，所以要进行重要度与编号的映射。这时再读题：“每座岛都有自己的独一无二的重要度”，感觉别有用心）
关键代码：
并查集：
查找：
点击查看代码
int getfather(int x)
{
if(father[x]!=x)
father[x]=getfather(father[x]);
return father[x];
}
点击查看代码
for(int i=1;i<=n;i++)
father[i]=i;
二分查询：
点击查看代码
int Query(int u,int z)
{
if(tr[u].val注意2：输出的是值映射的点的编号 \(Mp_x\)。
建桥操作：
点击查看代码
while(q--)
{
char op;
int x,y;
scanf("%s%d%d",&op,&x,&y);
if(op=='Q')
printf("%d\n",Query(root[getfather(x)],y));
else
{
int fx=getfather(x),fy=getfather(y);
father[fy]=fx;
Merge(root[fx],root[fy],1,n);
}
}
3.【HNOI2009】梦幻布丁
题意：
动态连续段修改与全局查询。
思路：
对于每一种颜色建一棵线段树，维护当前颜色段数，以及当前区间最左和最右是否为此颜色（\(pushup\) 和合并时用）。
对于修改操作，即为线段树合并，易证任意一种颜色只会被修改一次颜色，所以这个合并是无后效性的。
对于全局查询操作，可以记录一个全局答案 \(ans\)，初值为最开始建树后所有颜色的初始段数，在每次合并时实时修改。
关键代码：
建树：
点击查看代码
void BuildTree(int &u,int x,int y,int z)
{
if(u==0)
u=++tot;
if(x==y)
{
tr[u].val=1;
tr[u].ls=tr[u].rs=0;
tr[u].Lt=tr[u].Rt=1;
return;
}
int mid=x+y>>1;
if(z<=mid)
BuildTree(tr[u].ls,x,mid,z);
else
BuildTree(tr[u].rs,mid+1,y,z);
tr[u].Lt=tr[tr[u].ls].Lt;
tr[u].Rt=tr[tr[u].rs].Rt;
tr[u].val=tr[tr[u].ls].val+tr[tr[u].rs].val-(tr[tr[u].ls].Rt&tr[tr[u].rs].Lt);
}
点击查看代码
int Merge(int u1,int u2,int x,int y)
{
if(!u1||!u2)
return u1+u2;
if(x==y)
{
tr[u1].val|=tr[u2].val;
tr[u1].Lt|=tr[u2].Lt;
tr[u1].Rt|=tr[u2].Rt;
return u1;
}
int mid=x+y>>1;
tr[u1].ls=Merge(tr[u1].ls,tr[u2].ls,x,mid);
tr[u1].rs=Merge(tr[u1].rs,tr[u2].rs,mid+1,y);
tr[u1].val=tr[tr[u1].ls].val+tr[tr[u1].rs].val-(tr[tr[u1].ls].Rt&tr[tr[u1].rs].Lt);
tr[u1].Lt=tr[tr[u1].ls].Lt;
tr[u1].Rt=tr[tr[u1].rs].Rt;
return u1;
}
合并解释：模板，最后的 \(pushup\) 操作同建树。
小结：
很妙的思维题，虽然代码比较模板但是思维很精髓。
3.总体小结
线段树合并操作很死板，题目主要考察的是如何建树，合并什么东西。事实上以上的例题思维难度全在线段树表示的是什么上。而且线段树合并是个很难想到的算法，一般遇到这种题不会第一时间想到线段树合并。
不过据说线段树合并很少考，所以只需要掌握思想就行了，况且这个思想并不复杂。