柒葉灬 的博客

柒葉灬 的博客

线段树合并(个人笔记15)

posted on 2018-12-09 22:09:13 | under 专题总结 |

线段树合并


前置技能:动点开线段树。

线段树合并就是两个线段树进行合并,将每个节点的信息重新计算,然后返回。

模板

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