CVBB ACM Team

这是本文档旧的修订版！

内容：个人感觉讲得不够清楚，需要反复看几遍，并结合代码才能大致看懂。建议用形式化的语言写明合并过程，在简介部分举例（有图最好）等方法改进。另外这个复杂度怎么是个玄学。。没有严谨一点的证明吗？建议再检索一下资料。

线段树合并

简介

~~线段树合并是怎么回事呢？线段树大家应该很熟悉，那么…~~

有时候会遇到树上每个点开一个桶或者一个线段树，然后在$\text{dfs}$过程中不断合并的情况，一般权值线段树可以替代桶，然后又因为线段树有较好的合并性质，所以就有了线段树合并的说法。

一般来说关键步骤就是动态开点和线段树的合并操作：

因为不可能真的在每个点建一棵完整的线段树（而且一般情况下每个点所代表的权值都只是完整线段树的小部分），所以要动态开点

void update(int &id,int l,int r,int pos,int k)
{
    if(!id) id=++tot;  // 动态开点
    if(l==r){
        // 更新操作
        return ;
    }
    int mid = (l+r)>>1;
    if(pos<=mid) update(tr[id].lc,l,mid,pos,k);
    else update(tr[id].rc,mid+1,r,pos,k);
    push_up(id);
}

然后合并的操作主要基于两棵线段树具有相同的值域所以有相同的结构，那么递归的处理左右子树即可

int mergE(int p,int q,int l,int r)
{
    if(!p)return q;if(!q)return p;
    if(l==r){
        // merge_leaf 操作
        return p;
    }
    int mid = (l+r)>>1;
    tr[p].lc = mergE(tr[p].lc,tr[q].lc,l,mid);
    tr[p].rc = mergE(tr[p].rc,tr[q].rc,mid+1,r);
    push_up(p);
    return p;
}