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

>开始前先$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，返回 代码大概长这样： ```cpp 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](http://codeforces.com/problemset/problem/600/E) 题意：给你一棵有$n$个点的树$(n\leq10^5)$，树上每个节点都有一种颜色$ci(ci\leq n)$，让你求每个点子树**出现最多的颜色/编号的和** 不好意思，我实在太菜了，被题意杀了好几发，所以强迫症的断了一下句，希望有助于大家理解。 这题只要dfs一下，将每个子节点的线段树与父亲节点线段树合并，再将父亲节点的颜色插入该节点对应的线段树，然后直接查询答案就可以了。 以及**[远程评测BUG](https://www.luogu.org/discuss/lists?forumname=CF600E)**QAQ 代码长这样： ```cpp #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雨天的尾巴](https://www.luogu.org/problemnew/show/P4556) 这题的话主要是差分的思想，把每条覆盖路径离线下来，分解成$(u,lca(u,v))$,$(v,lca(u,v))$两条路径，在$u$点和$v$点将$z$位置$+1$,在$lca(u,v)$和$fa(lca(u,v))$的位置分别$-1$就可以了。每个点直接查询最大值，即为答案。 [牛客网NOIP赛前集训营-提高组（第一场）T3 保护](https://www.nowcoder.com/acm/contest/172/C) 首先还是要差分一下，这题可以转化为求子树中第$k$浅的链所在的位置，线段树合并完就是权值线段树查询$k$大值得内容了，最后答案是当前点的深度减去找到的点的深度与$0$取个较大值就可以了 [洛谷P3224永无乡](https://www.luogu.org/problemnew/show/P3224) 因为只有新增的桥，我们会想到并查集，问题转化成如何求一个并查集里的$k$小值，怎么办呢？当然是线段树合并了！我们在将$x$搞成$y$的父亲是顺便把$y$的线段树合并到$x$上就可以啦,接着就是权值线段树查询$k$小值的内容，显然不用再讲了。 [NOIP 2016D1T2天天爱跑步](https://www.luogu.org/problemnew/show/P1600) 某同学要求加一道线段树合并在提高组的应用，那就这题吧qwq 考虑把一个人的路径拆成$from$到$lca$和$lca$到$to$两段，差分一下用线段树维护 具体的操作是对起点插入$deep[from]$，终点插入$2*deep[lca]-deep$起点，相当于把起点沿$lca$翻上去。 然后线段树合并一波就搞定了 查询的是距离每个点$deep+wj$和$deep-wj$的点有几个 对了，闲(yi)得(jing)无(A)聊(K)的同学们可以玩玩这道题[CF666E](http://codeforces.com/problemset/problem/666/E) 标算好像是广义后缀自动机+线段树合并来着