[模板] 线段树合并

深藏阁楼爱情的钟 2023-08-17 17:16 121阅读 0赞

## 线段树合并 ##

把若干棵叶子节点总数为 \\(n\\) 的线段树通过某种顺序合并成一棵线段树. 时间复杂度 \\(O(n \\log n)\\).

### 时间复杂度分析 ###

考虑两颗线段树合并, 复杂度为这两颗线段树的相同节点个数. 这可以看作是删除的节点个数.

那么所有线段树合并, 所有节点最多被删除一次. 时间复杂度即为 \\(O(n \\log n)\\).

线段树合并的空间复杂度也为 \\(O(n \\log n)\\), 而可持久化的线段树合并 (见下) 使用的空间不超过 \\(2 \\cdot n\\log n\\).

### 普通的线段树合并 ###

把 `rt1` 变为 `rt1` 和 `rt2` 的并.

int merge(int rt1,int rt2){
        if(rt1==0||rt2==0)return rt1+rt2;
        ls(rt1)=merge(ls(rt1),ls(rt2));
        rs(rt1)=merge(rs(rt1),rs(rt2));
        pu(rt1);
        return rt1;
    }

### 可持久化线段树合并 ###

建立新树为两棵树的并.

int merge(int rt1,int rt2){
        if(rt1==0||rt2==0)return rt1+rt2;
        int rt=++pnd;
        ls(rt)=merge(ls(rt1),ls(rt2));
        rs(rt)=merge(rs(rt1),rs(rt2));
        return rt;
    }

[https://wenku.baidu.com/view/88f4e134e518964bcf847c95.html][https_wenku.baidu.com_view_88f4e134e518964bcf847c95.html]

转载于:https://www.cnblogs.com/ubospica/p/10250373.html

[https_wenku.baidu.com_view_88f4e134e518964bcf847c95.html]: https://wenku.baidu.com/view/88f4e134e518964bcf847c95.html

发表评论取消回复

表情：

评论列表（有 0 条评论，121人围观）

还没有评论，来说两句吧...

相关阅读

相关 [模板] 线段树合并

线段树合并把若干棵叶子节点总数为 \\(n\\) 的线段树通过某种顺序合并成一棵线段树. 时间复杂度 \\(O(n \\log n)\\). 时间复杂度分析考

深藏阁楼爱情的钟/ 2023年08月17日 17:16/ 0 赞/ 122 阅读

相关线段树模板

P3372 【模板】线段树 1 include<cstdio> include<iostream> using namespace std;

小咪咪/ 2023年08月17日 17:08/ 0 赞/ 111 阅读

相关线段树模板

public class Main { public static void main(String[] args) {

浅浅的花香味﹌/ 2022年10月05日 01:53/ 0 赞/ 159 阅读

相关线段树模板（模板）

参考博客 http://blog.csdn.net/metalseed/article/details/8039326 持续更新。。。 \[外链图片转存失败,源站可能有防盗

野性酷女/ 2022年09月24日 05:19/ 0 赞/ 190 阅读

相关 //线段树模板

先摆模板。。。 //线段树模板 struct line \{ int left,right;//左端点、右端点 int n;//记录这条线段出现了多少次，默认

偏执的太偏执、/ 2022年08月14日 04:54/ 0 赞/ 214 阅读

相关线段树模板+详解

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点\[a,b\]，它

淩亂°似流年/ 2022年06月17日 03:42/ 0 赞/ 195 阅读

相关线段树模板

洛谷oj:[点我][Link 1] 线段树区间修改区间查询 include<iostream> include<cstdio> include<cm

小灰灰/ 2022年05月16日 05:39/ 0 赞/ 230 阅读

相关二维线段树模板

-------------------- title: 二维线段树模板 date: 2018-10-31 15:21:44 tags: \- 二维线段树 c

以你之姓@/ 2022年04月22日 02:26/ 0 赞/ 254 阅读

相关序列操作（线段树，模板）

n个数，m次操作若a==1，求区间b-c最大值若a==2，将a\[ b \]改为c include<iostream> include<cstdi

小鱼儿/ 2022年01月07日 13:53/ 0 赞/ 246 阅读

相关线段树合并

前言线段树合并虽说是比较基础的内容，且我一直都知道大概的实现方式，但直到最近我才正式去写过一次，我真的太弱了啊。下面从暴力合并开始，依次介绍几种线段树合并的方式。

怼烎@/ 2021年12月01日 14:24/ 0 赞/ 362 阅读