线段树合并三十天：从入门到放弃

前言

由于各种原因，我的博客已经有一个月没有更新了。今天，我来写一片博客：能把你弄崩溃的$\text{线段树合并}$

一、前置知识

• 动态开点线段树
• 权值线段树

如果不会的我没法帮你

二、线段树合并简介

线段树合并，就是建立一棵新的线段树保存原有的两颗线段树的信息。

图片来源于某人的线段树合并讲义

一波凌云踏步再加一个托马斯回旋非常漂亮！

但是！咋做呢？

别急，我来给你讲讲看

1. 如果a有pos位置，b没有，那么新的线段树pos位置赋成a，返回
2. 如果b有pos位置，a没有，赋成b，返回
3. 如果此时已经合并到两棵线段树的叶子节点了，就把b在pos的值加到a上，把新线段树上的pos位置赋成a
4. 递归处理左子树
5. 递归处理右子树
6. 用左右子树的值更新当前节点
7. 将新线段树上的pos位置赋成a

是不是很懵逼？别急，我来给你一个example：

假设一个线段树为：

而另一个线段树为

则他们合并起来则是：

代码：

int merge(int a,int b,int l,int r)
{if(!a) return b;if(!b) return a;if(l==r){return a;}int mid=(l+r)>>1;tr[a].l=merge(tr[a].l,tr[b].l,l,mid);tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);push_up(a);return a;
}

妙啊！

三、时间复杂度

我最害怕的就是计算时间复杂度惹！
——某位巨佬

关于时间复杂度好不好算，有一个公式：

【数据删除】(我不会）

不过可以看这位dalao的blog

首先我们需要知道动态开点线段树中插入一个点会加入多少个新的节点？
线段树从顶端到任意一个叶子结点之间有$\log n$层，每层最多新增一个节点。
所以插入一个新的点复杂度是$\log n$的。

两棵线段树合并的复杂度显然取决于两棵线段树重合的叶子节点个数，假设有$m$个重合的点，这两棵线段树合并的复杂度就是 $m\log n$了，所以说，如果要合并两棵满满的线段树，这个复杂度绝对是远大于 $\log n$级别的。
也就是说，千万不要以为线段树合并对于任何情况都是 $\log n$的！

别崩溃，因为它一均摊，$10^5$至少能过

四、用处

这玩意有啥用呢？这个玩意可以处理一些用其他数据结构不好处理的子树问题
你对每个点开一棵线段树然后能维护的东西，线段树合并都能维护，因为他们的本质是一样的。

五、例题

CF600E

大意：

给你一棵有 $n$个点的树$n\le 10^5$，树上每个节点都有一种颜色 $c_i,c_i\le n$，让你求每个点子树出现最多的颜色/编号的和

洛谷P4556

洛谷P3224

洛谷P1600

CF666E