用一个新的线段树（也可是原先中的一个）包含两个原线段树的信息便是线段树的合并。
由于基础的线段树son为i*2和i*2+1需4倍空间且下标无法改变的缺点，在需合并的情况下就要使用动态开点线段树。
多开一个数组son[N][2]记录每个点的儿子位置。（其实真的很简单:）
void build(int L,int R,int l,int r,int now) { if(l==r) { t[now]=a[l]; return; } int m=l+r>>1; if(L<m) son[now][0]=++tot,build(L,R,l,mid,tot); if(R>m) son[now][1]=++tot,build(L,R,mid,r,tot); pushup(now); }
两树维护的内容需具有可合并性才可合并，如区间和、区间最值都可以。
以区间和为例。
int merge(int now1,int now2)///将2号树合并到1号上 { if(!now1||!now2)return now1+now2; t[1][now1]+=t[2][now2]; son[now1][0]=merge(son[now1][0],son[now2][0]); son[now2][0]=merge(son[now2][0],son[now2][0]); return now1; }
原文：https://www.cnblogs.com/29taorz/p/15150386.html