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

开始前先neta个小剧场
某次模拟赛前两天
本蒟蒻：“雨天的尾巴怎么写啊？我被日推了。”
大佬：“线段树合并啊，瞎搞搞就行了。”
本蒟蒻：“哦，那想必提高组不会考”
然后就爆零了，于是赶紧抢救一下，写下这篇博客，如果有误，还请大佬指正

零、前置算法：动态开点线段树和权值线段树

感觉动态开点线段树和普通线段树的区别比较明显的就是x的左儿子和右儿子不一定是x*2(x<<1)和x*2+1(x<<1|1)而是要另外储存一下。

其实如果你学的是结构体线段树，在写动态开点的时候应该不会有任何违和感……

动态开点线段树有着一些优点，比如说当你让某个节点继承另一个节点的左儿子或者右儿子的时候，你可以不用新建一棵线段树，而是直接将该节点的左右儿子赋成那个节点的左右儿子就行了，总之就是空间上有一定的优越性。

线段树合并如果要每次都完整建一棵线段树的话，怕不是建完树就好凉凉了，因此我们需要选择动态开点。

权值线段树能代替平衡树做一些求k大、排名、找前驱后继的操作，了解一下就可以啦

一、线段树合并的思想

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

图片来源于主席的线段树合并讲义
这个思想非常简单，假设我们现在合并到了两棵线段树a、b的pos位置，那么

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

代码大概长这样：

    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;
    }

好的，思路是不是很简单？ 所以问题来了，这么搞的复杂度是多少？

二、线段树合并的复杂度证明

这道题也就最多合并100000棵满线段树，一遍复杂度也就是O(logn)，所以不是显然能过的嘛
--by 某天天算错复杂度的神仙

上面那个神仙是谁，我们姑且不谈。

先来思考一下在动态开点线段树中插入一个点会加入多少个新的节点
线段树从顶端到任意一个叶子结点之间有logn层，每层最多新增一个节点
所以插入一个新的点复杂度是logn的

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

那么为什么数据范围10^5的题目线段树合并还稳得一批？
这是因为logn的复杂度仅适用于插入点少的情况。
如果n与加入的总点数规模基本相同，我们就可以把它理解成每次操作O(logn)

来证明一下：
假设我们会加入k个点，由上面的结论，我们可以推出最多要新增klogk个点。
而正如我们所知，每次合并两棵线段树同位置的点，就会少掉一个点，复杂度为O(1)，总共klogk个点，全部合并的复杂度就是O(klogk)

可见，上面那个证明是只与插入点个数k有关，也就是插入次数在10^5左右、值域10^5左右的题目，线段树合并还是比较稳的。

至于更快的方法？
网上有说可以用可并堆的思路合并，我太菜了，并没有试过，所以就点到为止了~

对了，由上可知，因为插入klogk个节点，所以线段树合并的空间复杂度也是O(klogk)的

三、线段树合并的用处

处理一些用其他数据结构不好处理的子树问题
大概是本来你对每个点开一棵线段树然后能维护的东西，线段树合并都能维护，因为他们的本质是一样的

常见的比如说查询子树内前驱后继第k大，或者x是第几大之类的权值线段树能干的各种事

以及出现最多的数，总和最大的数，这些权值线段树也能干的事

暂时还没有见过不是权值线段树的线段树合并。猜测一下大概是因为这种线段树合并复杂度会很鬼畜？

如果有的话也请大佬分享一下啦~

upd.应大佬建议来贴一道题完整代码
CF600E
题意：给你一棵有n个点的树(n\leq10^5)，树上每个节点都有一种颜色ci(ci\leq n)，让你求每个点子树出现最多的颜色/编号的和

不好意思，我实在太菜了，被题意杀了好几发，所以强迫症的断了一下句，希望有助于大家理解。

这题只要dfs一下，将每个子节点的线段树与父亲节点线段树合并，再将父亲节点的颜色插入该节点对应的线段树，然后直接查询答案就可以了。

以及远程评测BUGQAQ

代码长这样：

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson tr[now].l
#define rson tr[now].r
#define int long long
using namespace std;

struct tree
{
    int l,r,sum,val,ans;
}tr[5000050];

int rt[100010],cl[100010],cnt,n,anss[100010];
vector<int> g[100010];

int push_up(int now)
{
    if(tr[lson].sum>tr[rson].sum)
    {
        tr[now].sum=tr[lson].sum;
        tr[now].val=tr[lson].val;
        tr[now].ans=tr[lson].ans;
    }
    if(tr[rson].sum>tr[lson].sum)
    {
        tr[now].sum=tr[rson].sum;
        tr[now].val=tr[rson].val;
        tr[now].ans=tr[rson].ans;
    }
    if(tr[lson].sum==tr[rson].sum)
    {
        tr[now].sum=tr[lson].sum;
        tr[now].val=tr[lson].val;
        tr[now].ans=tr[lson].ans+tr[rson].ans;
    }
}

int update(int &now,int l,int r,int pos,int v)
{
    if(!now) now=++cnt;
    if(l==r)
    {
        tr[now].val=l;
        tr[now].sum+=v;
        tr[now].ans=l;
        return 0;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(lson,l,mid,pos,v);
    else update(rson,mid+1,r,pos,v);
    push_up(now);
}

int merge(int a,int b,int l,int r)
{
    if(!a) return b;
    if(!b) return a;
    if(l==r)
    {
        tr[a].val=l;
        tr[a].sum+=tr[b].sum;
        tr[a].ans=l;
        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;
}

int dfs(int now,int f)
{
    for(int i=0;i<g[now].size();i++)
    {
        if(g[now][i]==f) continue;
        dfs(g[now][i],now);
        merge(rt[now],rt[g[now][i]],1,100000);
    }
    update(rt[now],1,100000,cl[now],1);
    anss[now]=tr[rt[now]].ans;
}

int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&cl[i]);
        rt[i]=i;
        cnt++;
    }
    int from,to;
    for(int i=1;i<n;i++)
    {
        scanf("%lld%lld",&from,&to);
        g[from].push_back(to);
        g[to].push_back(from);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
    {
        printf("%lld ",anss[i]);
    }
}

一个小小的trick是在最早一次插入之前将所有点的根先编号，这样子可能即使写翻了也有概率A掉（因为rt[now]=now)

四、线段树合并与平衡树启发式合并的比较

splay启发式合并的思路大概是把一棵较小splay的值全部拿出来插到大的splay里，这样子复杂度大概是O(n(logn)^2)的，不过如果你按照较小的中序遍历的顺序插入，复杂度大概也是O(nlogn)级别的

但是但是，线段树合并代码这么短，能用线段树合并解决的题，为什么要去写平衡树启发式合并呢qwq

upd.大佬告诉蒟蒻splay合并的空间更优，可以达到O(n)，涨姿势了～

五、一些例题

洛谷P4556雨天的尾巴
这题的话主要是差分的思想，把每条覆盖路径离线下来，分解成(u,lca(u,v)),(v,lca(u,v))两条路径，在u点和v点将z位置+1,在lca(u,v)和fa(lca(u,v))的位置分别-1就可以了。每个点直接查询最大值，即为答案。

牛客网NOIP赛前集训营-提高组（第一场）T3 保护
首先还是要差分一下，这题可以转化为求子树中第k浅的链所在的位置，线段树合并完就是权值线段树查询k大值得内容了，最后答案是当前点的深度减去找到的点的深度与0取个较大值就可以了

洛谷P3224永无乡
因为只有新增的桥，我们会想到并查集，问题转化成如何求一个并查集里的k小值，怎么办呢？当然是线段树合并了！我们在将x搞成y的父亲是顺便把y的线段树合并到x上就可以啦,接着就是权值线段树查询k小值的内容，显然不用再讲了。

NOIP 2016D1T2天天爱跑步

某同学要求加一道线段树合并在提高组的应用，那就这题吧qwq
考虑把一个人的路径拆成from到lca和lca到to两段，差分一下用线段树维护
具体的操作是对起点插入deep[from]，终点插入2*deep[lca]-deep起点，相当于把起点沿lca翻上去。 然后线段树合并一波就搞定了
查询的是距离每个点deep+wj和deep-wj的点有几个

对了，闲(yi)得(jing)无(A)聊(K)的同学们可以玩玩这道题CF666E
标算好像是广义后缀自动机+线段树合并来着