线段树合并（个人笔记15）

## 线段树合并 -------- _前置技能：动点开线段树。_ 线段树合并就是两个线段树进行合并，将每个节点的信息重新计算，然后返回。 #### 模板 ```cpp int merge(int x,int y){ if(!x||!y)return x|y; lson[x]=merge(lson[x],lson[y]); rson[x]=merge(rson[x],rson[y]); sum[x]+=sum[y]; return x; } ``` ------ ### 时间复杂度（重点！！！） 合并线段树其实并没有多难，重点是要理解它的时间复杂度和空间复杂度。为什么时间复杂度只有$O(nlogn)$ 比如说，你总共开了$n$个线段树和$n$个点，最后合并成一棵线段树。  比如说上方这个图，$n=4$，一开始是4条链，这是合并后的图。 我们仔细观察上面的模板，可以发现： - $4,5,6,7$ : 第三层每一个点最多被**遍历**$1$次，总共$4$次 - $2,3$ : 第二层每一个点最多被**处理**$2$次，总共$4$次 - $1$ : 第一层的这个点最多被**处理**$4$次，总共$4$次。 得到复杂度：$n$ * 树的深度$dep$ 因为$dep=logn$ 所以复杂度就是$O(nlogn)$了 >_那么如果 点的个数>n 呢？，~~这时候怎么分析复杂度？~~，反正只要记住复杂度就是 $O(mlogn)$ 就对了！！（$m$表示点的个数）_ >>每递归logn次至少有2个点合并，所以合并m个点最多递归mlogn次 ------- ## 空间复杂度 这根据合并是否可持久化决定，若不可持久化，就是$O(mlogn)$（最初的$m$个点）。若可持久化，则空间大一倍左右（加上时间复杂度）。 ------- ## 适用题型 只要你知道了时间复杂度是怎么来的，那基本你看到一个题目就可以立马想到是不是线段树合并了，（除了专题最后一题毒瘤题）。 就是看有没有需要 **信息合并** 操作，是否可行还有看 **点的个数** 。 ------- ## （进阶）线段树合并->线段树拆分 线段树拆分适用于拆一个连续的区间，复杂度就是 （边界的个数*$logn$） ------ 每个算法最重要的是会用，能想到。 END