首页 > 其他分享 >线段树合并学习笔记

线段树合并学习笔记

时间:2023-08-08 15:25:58浏览次数:44  
标签:maxid lc int 线段 合并 笔记 date root

基本思路

线段树合并其实就是简单的暴力合并就可以了。一般是运用于权值线段树。通常是在每个节点都需要要一颗线段树才能维护答案,且有多个节点时,会使用线段树合并。但每个节点所有的权值不能太多,如果都是比较满的二叉树的话,时间复杂度就会很高。

通常,加入值的数量跟节点数量在同一级别的话,时间复杂度是\(O(n\log n)\) 级别的(但其实我不是很确定)。

具体代码

其实代码理解了之后就是非常简单的了。

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=200011;
struct node{
	int to,lt;
}e[N<<1];
int last[N],tot;
void add(int u,int v){//连边 
	e[++tot].lt=last[u];
	e[tot].to=v;
	last[u]=tot;
	return ;
}
int dep[N],son[N],size[N],fa[N]; 
void dfs1(int u,int fat){//树剖求lca 
	dep[u]=dep[fat]+1;size[u]=1;fa[u]=fat;
	for(int i=last[u];i;i=e[i].lt){
		int v=e[i].to;
		if(v==fat)continue;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[son[u]]<size[v])son[u]=v;
	}
}
int top[N];
void dfs2(int u,int top_u){
	top[u]=top_u;
	if(son[u])dfs2(son[u],top_u);
	for(int i=last[u];i;i=e[i].lt){
		int v=e[i].to;
		if(!top[v])dfs2(v,v);
	}
}
int root[N];
int lca(int a,int b){
	while(top[a]!=top[b]){
		if(dep[top[a]]<dep[top[b]])swap(a,b);
		a=fa[top[a]];//树剖这里记得是fa 
	}
	if(dep[a]>dep[b])swap(a,b);
	return a;
}
struct tree{
	int lc,rc,date,maxid;
}t[N*30];
int cnt;
void update(int x){//更新节点 
	if(t[t[x].lc].date>=t[t[x].rc].date)t[x].maxid=t[t[x].lc].maxid;
	else t[x].maxid=t[t[x].rc].maxid;
	t[x].date=max(t[t[x].lc].date,t[t[x].rc].date);
	return ;
}
void change(int &x,int l,int r,int k,int val){//修改 更新某个节点上权值线段树的值 
	if(!x)x=++cnt;//动态开点,没有就建立一个新的节点 
	if(l==r){
		t[x].date+=val;
		t[x].maxid=l;
		return ;
	}
	int mid=(l+r)>>1;
	if(k<=mid)change(t[x].lc,l,mid,k,val);
	else change(t[x].rc,mid+1,r,k,val);
	update(x);return ;
}
int merge(int a,int b,int l,int r){
	if(!a)return b;if(!b)return a;//如果一个没有就返回另一个 
	if(l==r){
		t[a].date+=t[b].date;
		t[a].maxid=l;
		return a;
	}
	int mid=(l+r)>>1;
	t[a].lc=merge(t[a].lc,t[b].lc,l,mid);//由合并方式可以看出,如果每颗权值线段树都很满的话 
	t[a].rc=merge(t[a].rc,t[b].rc,mid+1,r);//时间复杂度是会很高的 
	update(a);
	return a;
}
int ans[N];
#define maxn 100000
void work(int u){//从下往上合并线段树 
	for(int i=last[u];i;i=e[i].lt){
		int v=e[i].to;
		if(v==fa[u])continue;
		work(v);
		root[u]=merge(root[u],root[v],1,maxn);
	}
	if(t[root[u]].date)ans[u]=t[root[u]].maxid;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs1(1,0);dfs2(1,1);
	for(int i=1;i<=m;i++){
		int x,y,z,u;
		cin>>x>>y>>z;
		u=lca(x,y);
		//运用树上差分的思想 
		change(root[x],1,maxn,z,1);change(root[y],1,maxn,z,1);
		change(root[u],1,maxn,z,-1);change(root[fa[u]],1,maxn,z,-1);
	}
	//cout<<endl;
	work(1);
	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
	return 0;
} 

标签:maxid,lc,int,线段,合并,笔记,date,root
From: https://www.cnblogs.com/shadom/p/17614403.html

相关文章

  • STC15 外部中断编程笔记
    以STC15W4K58S4为例,可以将片上的外部中断资源分为“高级”和“低级”两类,EXINT0和EXINT1属于高级的,EXINT2~EXINT4属于低级的。“高级”的外部中断可以配置中断优先级,选择中断源;低级的则不行。EXINT0和EXINT1的配置这两个外部中断的配置寄存器都可位寻址,因此可以直......
  • 复习笔记|《计算机组成原理》
    参考教材:《计算机组成原理》蒋本珊➢前2类题看书中和课件中的有关概念。➢第3、4、5类题请注意平时的作业。如:❑扩展操作码设计❑有效地址的计算❑定点数乘、除运算❑存储器设计❑Cache计算❑微指令操作控制字段的设计第一章➢存储程序概念计算机硬件的组成,存储器控......
  • [学习笔记] Switch语句使用“===”进行比较
    JS中,switch语句会使用恒等计算符(===)进行比较。如上所述,下列代码中因为x定义为字符串10,而case为数字10,因此将不会弹出“HelloWorld”:var x="10";switch(x){    case 10:alert("Hello");}实际应用时应注意这点。......
  • 【刷题笔记】9. Palindrome Number
    题目Determinewhetheranintegerisapalindrome.Aninteger is a palindromewhenit readsthesamebackwardasforward.Example1:Input:121Output:trueExample2:Input:-121Output:falseExplanation:Fromlefttoright,itreads-121.Fromrightto......
  • 《从0到1:JavaScript快速上手》笔记(一)
    一、两个十分有用的方法document.write():表示在页面输出一个内容alert():表示弹出一个对话框二、变量与常量在JavaScript中,变量指的是一个可以改变的量,也就是说,变量的值在程序运行过程中是可以改变的。(1)在JavaScript中,给一个变量命名,我们需要遵循以下2个方面的原则。变量有字母、......
  • RotatE 学习笔记
    目录RotatEWhatisRotatE?MotivationModelNegativesamplingLossfunctionExperimentsOthersSummaryRotatEpaper:RotatE:KnowledgeGraphEmbeddingbyRelationalRotationinComplexSpaceWhatisRotatE?本文是北大和加拿大的研究团队发表在ICLR2019上的文章,提出了......
  • 图论学习笔记
    图图论绘图在线图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系!点一般用字母v表示,如v1,v2,v3,v4一些简单的术语:路径:一些边组成的序列,满足第一条边的终点......
  • protobuf学习笔记
    1下载protoc编译器源代码和可执行文件下载:下载地址可根据不同的系统,下载对应的可执行文件,用于编译.proto文件示例C++的命令方式为:protoc.exe--cpp_out=./demo.proto,就可以生成对应的demo.pb.h和demo.ph.cc源代码安装vcpkg下载地址forwindows:>gitclonehttps://githu......
  • win7系统笔记本作为wifi热点提供无线连接
    只有有线没有路由器的可以用win系统的笔记本设置,给手机或者其他的笔记本提供无线连接 步骤如下:首先确认你的无线网卡可以使用。在开始菜单中依次找到“所有程序”--“附件”--“命令提示符”,右键“以管理员身份运行”。如下图所示:在“命令提示符”里输入“netshwlansethost......
  • Java读取Excel中的合并单元格
    1、 Maven仓库下载导入在pom.xml中配置maven路径,指定依赖,如下:<dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId><version>4.1.1</version></dependency><dependency><groupId>......