首页 > 其他分享 >线段树分裂合并

线段树分裂合并

时间:2023-03-14 17:23:50浏览次数:42  
标签:int 线段 合并 now1 分裂 复杂度 节点

概述

  • 线段树分裂这里暂时没有。

  • 线段树合并是指将管辖范围相同的两棵线段树对位(节点意义下)合并。

线段树合并

  • 线段树合并支持各种统计子树的操作。
    • 详细来讲就是,考虑某个题目给出一棵树(相对于普通线段树题目的数组而言,这里是每个树上点都对应着一个数组,不过父子之间数组差异往往较小),然后要询问某些子树中的结合性问题。

    • 首先肯定有一种暴力做法就是对于每个子树都建一棵树。不过显然即使动态开点也会 \(MLE\),时间复杂度更不必谈了,建树远高于 \(n\log_2 n\)(因为大部分线段树要处理复数个数组)。

    • 考虑利用树的性质:当前子树的结合性问题解=结合解(当前点,各个子树)。这种结合往往就是节点对位相结合,最多再维护一下。

    • 所以我们先给每个点开一棵线段树(动态开点,不必真的开出来)。然后自上而下 dfs 一遍,先递归求解子树内的问题,然后将子树的线段树合并到当前节点上,最后回答当前子树的问题。

实现原理

离线线段树合并

  • 合并后子树的线段树的信息丢失,必须离线问题,自下而上回答(当然实际操作是 dfs 递归求解)。优点是空间(合并时不会开新节点)。

  • 先放代码,这也是典型的不看代码就是虚空讲解的算法。

il int merge(int now1,int now2,int l,int r){
	if(!now1 || !now2) return now1|now2;
	if(l==r){sum[now1]+=sum[now2]; return now1;}
	ls[now1]=merge(ls[now1],ls[now2],l,mid);
	rs[now1]=merge(rs[now1],rs[now2],mid+1,r);
	pu(now1); return now1;
}
  • 可以看到,这种合并的核心原理是如果都有就把第二棵的加到第一棵上,如果一方没有就直接模仿主席树进行连边(如果本来就是\(now1\)的子树就不用重新连边了)。

  • 可见,一定不会新建节点,只有一方有的节点不会进入。纸面单次合并复杂度为 \(O(n_{both}\log_2 n_{both})\),即总共同节点数。

  • 实际上,假设整棵树一共操作了 \(n\) 次(必须是单点修改,或者说每次修改至多开满一条独特链),那么将所有线段树合并成\(1\)个的总复杂度是大常数 \(O(n\log_2 m)\)。

  • 这一结论可以通过势能分析给出:

    • 合并开始前的 \(n\) 次操作每次至多开满一条链,线段树高 \(\log_2 m\),总复杂度 \(O(n\log_2 m)\)。

    • 合并时,每个节点都至多被 dfs 到一次,因为假如两者都有某节点那其中某个节点就再也不用,只有一方有的节点根本没有进去(\(O(1)\) 连边可以算成它父亲节点的常数,不影响,毕竟线段树是二叉树)。既然总点数至多为 \(O(n\log_2 m)\),那么合并的总复杂度也就是大常数 \(O(n\log_2 m)\)。

在线线段树合并

  • 模仿主席树,每次合并出的新树是一个新根,相加的点是新建的,只有一方的点是连边,然后以后再修改就和主席树一样。

  • 从而子树的线段树信息不丢失,可以在线回答问题。

  • 时间复杂度和上面基本一样(只有一方的点也是不进),但常数略大(开新点)。

  • 空间复杂度等于时间复杂度(访问到的点数也就是新开的点数,最多三倍罢了)。我还没写过,写了会补上。

例题

P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

  • 维护区间最大数的 \(pos\)。

P3224 [HNOI2012]永无乡

  • 不断进行合并,维护连通块(并查集)中的第 \(k\) 小。

线段树分裂

  • 鉴于我现在不想写博客,我们只扔一下代码并说一下注意事项:
il void splitv(int now,int l,int r,int k,int &x){
	x=newnode();
	if(k<=mid){
		a[x].rs=a[now].rs,a[now].rs=0;
		if(l==r) return;
		splitv(a[now].ls,l,mid,k,a[x].ls);
	}
	else{
		a[now].ls=a[now].ls,a[x].ls=0;
		if(l==r) return;
		splitv(a[now].rs,mid+1,r,k,a[x].rs);
	}
	pu(now),pu(x); return;
}
  • 这是一个按值域分裂的例子。有理由认为按数量分裂也是可以的。

  • 在传统的 fhq 分裂中,我们会有 &x,&y。但这里我们却钦定保留在 \(now\) 处,理由主要在于,如果把 &x 置为 \(rt\) 一路操作过来的话,因为两者都取引用,故两者无法分成真正的两个东西(除非不让 \(y=now\))。故必须以这种方式实现。

标签:int,线段,合并,now1,分裂,复杂度,节点
From: https://www.cnblogs.com/weixin2024/p/17215639.html

相关文章

  • 力扣简21 合并两个有序链表
    递归特别短!没这种思维!  自己用那种最直白的两个两个相比换指针指向导致会有空情况等特殊情况出错 看了题解是用递归什么的扩展一下这种思路而且可以采用给链表加......
  • CF915E 题解(动态开点线段树)
    题目传送门简要题意:题面就挺简要的。看到题目第一眼想到线段树,再看一眼数据范围,\(1≤n≤10^9\),寄,既然不能直接用线段树,那怎么办呢?可以离散化,为了避免麻烦的离散化,......
  • 合并使用不同语言的两个字幕
    合并使用不同语言的两个字幕这个在线工具将两个字幕文件合并为一个,使您可以同时看到使用两种语言的字幕。有了这个工具,您可以节省时间,因为您不需要在词典中查找生词的翻译......
  • 【230312-6】给定双曲线x^2-y^2/2=1,过点A(2,1)的直线l,与所给的双曲线交于P1,P2,线段P1,P2的
    ......
  • 合并集合
       合并集合:1.将两个集合合并2.询问两个集合是否在一个集合中如何求树根的编号:往上走如何合并两个集合:px是x的集合编号,py是y的集合编号,合并直接px=y。(给px找了个爸......
  • numpy中数据合并,stack ,concentrate,vstack,hstack
    numpy中数据合并,stack,concentrate,vstack,hstackhttps://www.cnblogs.com/onemorepoint/p/9541761.htmlhttps://blog.csdn.net/sdnuwjw/article/details/100540882https:......
  • JUC(七)分支合并框架
    JUC分支合并框架简介Fork/Join可以将一个大的任务拆分成多个子任务进行并行处理,最后将子任务的结果合并称为最终的计算结果。Fork:负责将任务拆分Join:合并拆分任务For......
  • 华为OD机试 数组合并
    数组合并......
  • 合并同一个目录下的多张excel表
    目的将同一目录下的表格1和表格2合并到一张新表new_file.xlsx中目录如下合并操作的代码如下点击查看代码importpandasaspdimportos#文件路径file_dir=r'......
  • excel 合并
    最近整理收钱吧的账单明细,因为收钱吧限制每次最多只能导出1个月的明细,所以我需要合并这些零零碎碎的表格,方便在excel中做统计筛选#!/usr/bin/envpython3#coding:u......