浅谈线段树进阶用法(未完工)

xiao7Mr10

2026-03-24 16:36:54

发布于：重庆

652阅读

0回复

0点赞

前言

本文篇幅较长，里面包含了对线段树进阶用法的介绍和本人对此的理解，希望这篇文章能帮助你更好的掌握这些知识。(ps: 请你保证至少会基础线段树以及简单用法)

Update: 于 2025年8月1日完成动态开点还有部分可持久化线段树。

Update: 于 2025年8月20日完成可持久化线段树进阶内容。

线段树动态开点

一般而言，线段树是一颗完全二叉树。但是有些题目需要我们维护较大的值域信息，这时候一般的建树方法并不适用，所以我们需要使用动态开点的方法。

回顾线段树基本原理，在值域极大的情况下，线段树在查询或修改时有些节点我们可能从始至终都不会用到，此时就没有必要把这样的节点保存。换句话说，我们按需分配，只保存需要访问的节点，这样就可以做到合适的复杂度了。注意，此时就不能直接建树了，更不能使用堆式存储法（因为我们的节点是动态储存的）。

实现有两种主流方法：第一，用取地址符更新节点。第二，直接函数返回编号。个人更倾向于好写简洁的第一种方法。

void change(int &x,int l,int r,int s,int k){
  if(!x)x=++tot;//x不存在需要新建
  int mid=(l+r)>>1;
  if(s<=mid)change(c[x].ls,l,mid,s,k);
  else change(c[x].rs,mid+1,r,s,k);//修改逻辑不变
  update(x);//该干啥干啥 
}

上面列举的是单点修改的做法，我们可以把这个过程理解为向线段树添加若干条链，查询时就在这颗稀疏二叉树上正常访问即可。

int query(int x,int l,int r,int s,int t){
	if(!x)return 0;//返回一些对答案无影响值表示这是空节点,比如求和就可以返回0
	if(l>=s&&r<=t)return c[x].val;//正常返回
    //如果有区间修改就pushdown一下
	//以下查询结构是个人习惯，并且这种结构可以适用于合并结构体复杂信息，更加方便。 
	if(s>mid)return query(c[x].rs,mid+1,r,s,t);//只考虑右儿子 
	else{
		if(t<=mid)return query(c[x].ls,l,mid,s,t)//只考虑左儿子 
		return query(c[x].ls,l,mid,s,t)+query(c[x].rs,mid+1,r,s,t);//合并答案 
	}
}

对于区间修改而言，下传懒标记时我们需要判断左右儿子是否存在，如果不存在需要新建。(注意这里的空间开销不小)

void pushdown(int x,int l,int r){
  int mid=(l+r)>>1;
  if(!c[x].ls)c[x].ls=++tot;
  if(!c[x].rs)c[x].rs=++tot;
  //do something 
  c[c[x].ls].val=...,tag[c[x].ls]=...;
  c[c[x].rs].val=...,tag[c[x].rs]=...;
  tag[x]=;//标记清空 
}

当值域远大于操作规模时我们的空间复杂度大概是 $O(n \log V)$ 的，时间复杂度同理，但是需要注意的一点是区间修改下传标记所需要的额外开销，一般需要开 $30$ 到 $50$ 倍不等，建议在不超过空间限制的情况下尽量将数组开大一些以保证正确性。

这里附送一道例题，需要支持区间修改和区间查询：CF915E Physical Education Lessons

可持久化线段树

前置知识：动态开点线段树.

该部分篇幅较长，请读者根据需求自行选择阅读。

持久化数据结构基础介绍

" 可持久化数据结构 (Persistent data structure) 总是可以保留每一个历史版本，并且支持操作的不可变特性 (immutable)。 ----- 摘自 OIwiki

在很多题目中，我们可以通过离线思想配合扫描线等算法批量处理问题，以达到优化复杂度的目的。但有些题目需要我们处理在线操作，这时就需要可持久化数据结构了。

所谓可持久化数据结构，就是支持对维护信息的历史版本做查询和修改的数据结构。我们对可持久化数据结构的操作自由度将其分为四类：

部分可持久化：可以访问所有版本，但是只支持修改最新版本。
完全可持久化：所有版本都可以访问修改。
可合并可持久化：在完全可持久化的基础上，支持将两个历史版本合并。
函数式可持久化：函数式编程中实现的持久化数据结构，对象都是只读的，任意修改都是创建一个新的节点，而不是在旧节点上修改。

以上四种持久化是逐步增强的，后者包含于前者。在算法竞赛中，我们一般只在意前两种可持久化结构。

简介和说明

可持久化线段树，又被称之为主席树，由 NOI 选手黄嘉泰（HJT）发明。（有个有趣的说法，称其发明原因是发明者当时不会写划分树，从而用此结构替代)

而很多地方也称主席树为可持久化权值线段树，这些叫法五花八门，初学者需要理清这些概念，避免混淆，这里均使用全名可持久化线段树。

原理实现

首先我们先介绍一下权值线段树，就是对于一个固定的序列维护一颗线段树，每个数按其权值为下标插入线段树中并维护值域信息。容易发现，我们可以通过线段树二分的方式做到 $O(\log n)$ 的时间求全局第 $k$ 大。

由此，我们引出一道经典题目：给定由 $n$ 个正整数构成的序列 $a$ ，对于指定的闭区间 $[l, r]$ 查询其区间内的第 $k$ 小值。

首先，我们假设对区间 $[l,r]$ 内的树构造一颗值域线段树，那么问题就转化为了全局第 $k$ 大。我们发现，实际上每个数的出现次数可以差分处理。比如说我们需要计算 $[l,r]$ 内数 $x$ 的出现次数，就可以通过 $[1,r]$ 中 $x$ 的出现次数减去 $[1,l-1]$ 中 $x$ 出现的次数得到答案。

也就是说，我们可以参考前缀和的思想维护 $n$ 棵值域线段树，第 $i$ 棵线段树维护区间 $[1,i]$ 内的桶信息，查询时就可以通过对第 $r$ 棵线段树和 $l-1$ 棵线段树作差得到区间上线段树的实际信息。

至于如何维护这 $n$ 棵线段树，其实也不是一件麻烦事。沿用上文线段树动态开点的思想，容易发现第 $i$ 棵线段树的维护信息与第 $i-1$ 棵线段树仅有一个数 $a_i$ 之差，换到线段树上只是多了一条长度为 $\log n$ 的链而已。故用一个数组 $rt$ 记录每个线段树的根，记录左右儿子的基础上动态开点就可以了。

这里引用了 OIwiki 里的例子，下图表现了修改 $[1,8]$ 中 $1$ 的例子：

注意，我们实际上每次插入是直接新建节点的，与之前这个节点是否出现过无关。实际上，可持久化线段树形成的结构严格来说并不是一棵树，因为一个节点可能被多个父节点引用，但这并不影响我们查询信息。

插入的具体实现也是较为简单的，类似动态开点的技巧我们每次新建一个节点，再把前驱节点的信息复制给它，并对信息做相应的更新。

在值域不大的时候我们可以先建一颗空树，然后再像上图一样依次插入，就避免了空节点无法复用的麻烦。如果避免不了值域大的问题，我们就只能参考动态开点的方式每次新建节点。

事实上，由于线段树的树高在 $\log n$ 量级，所以每插入一个数我们所需要的空间是 $O(\log n)$ 左右，这意味着一颗可持久化线段树所需空间是 $O(n \log n)$ 量级的。

下面给出【模板】可持久化线段树 2 基于可持久化线段树的实现：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
struct tree{
  int siz,ls,rs;//出现个数，左儿子，右儿子 
}c[N<<5];//注意线段树节点个数需要开到O(nlogn)量级 
int n,m,l,r,k,rt[N],a[N],b[N],tot;
void update(int x){
  c[x].siz=c[c[x].ls].siz+c[c[x].rs].siz;//如果支持标记永久化的话这里可以不用 
}
void build(int &x,int l,int r){
  x=++tot;
  if(l==r)return;int mid=(l+r)>>1;
  build(c[x].ls,l,mid),build(c[x].rs,mid+1,r);
}
void insert(int &x,int y,int l,int r,int s){//注意，这里的x代表新插入的链，y代表所需要复用的节点信息，可以理解为在两个线段树上移动 
  x=++tot;c[x]=c[y];c[x].siz++;//新建，复用，更新信息(这里使用了标记永久化的技巧) 
  if(l==r)return;int mid=(l+r)>>1;
  if(s<=mid)insert(c[x].ls,c[y].ls,l,mid,s);
  else insert(c[x].rs,c[y].rs,mid+1,r,s);//update(x);
}
int query(int x,int y,int l,int r,int k){//表示第y颗线段树信息-第x颗线段树信息 
  if(l==r)return l;
  int mid=(l+r)>>1,val=c[c[y].ls].siz-c[c[x].ls].siz;//查询左子树信息 
  if(val>=k)return query(c[x].ls,c[y].ls,l,mid,k);
  else return query(c[x].rs,c[y].rs,mid+1,r,k-val);//注意，这里需要减去左子树的规模（即val）
}
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  cin >> n >> m;
  for(int i = 1;i <= n;i++)cin >> a[i],b[i]=a[i];
  sort(b+1,b+1+n);int len=unique(b+1,b+1+n)-b-1;
  for(int i = 1;i <= n;i++)a[i]=lower_bound(b+1,b+1+len,a[i])-b;//离散化 
  build(rt[0],1,n);//空树 
  for(int i = 1;i <= n;i++)insert(rt[i],rt[i-1],1,n,a[i]);
  for(int i = 1;i <= m;i++){
  	cin >> l >> r >>k;
  	cout << b[query(rt[l-1],rt[r],1,n,k)] << "\n";
  }
  return 0;
}

实际上很多可持久化线段树问题的空间限制非常宽松，我们完全可以和实现动态开点线段树时一样在不超空间的限制下尽可能多开线段树节点。

进阶用法

可持久化线段树实际上也有很多扩展用法，比如差分统计信息或处理偏序问题，建议读者在掌握其基础用法后再阅读本部分。

配合树上差分

在序列上查询信息我们可以通过差分达到目的，在树上我们可以通过树上差分的方式解决问题。

比如说这道题：P2633 Count on a tree，要求我们在线回答树上路径第 $k$ 小。

考虑树上差分的方式，我们用第 $i$ 颗线段树表示根节点 $1$ 到 $i$ 路径上所有点的信息。类似序列上的做法在深度优先搜索的时候顺便维护即可，查询时用树上差分的技巧维护链信息即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
struct Point{
  int ls,rs,siz;
}c[N*30];
int n,m,u,v,tot,a[N],b[N],len,siz[N],son[N],rt[N],top[N],f[N],de[N];
void build(int &x,int l,int r){
  x=++tot;
  if(l==r)return;int mid=(l+r)>>1;
  build(c[x].ls,l,mid);build(c[x].rs,mid+1,r);
}
void insert(int &x,int y,int l,int r,int s,int k){
  x=++tot,c[x]=c[y],c[x].siz++;
  if(l==r)return;int mid=(l+r)>>1;
  if(s<=mid)insert(c[x].ls,c[y].ls,l,mid,s,k);
  else insert(c[x].rs,c[y].rs,mid+1,r,s,k);
}vector <int> e[N];
void dfs(int u,int fa){siz[u]=1;
  insert(rt[u],rt[fa],1,len,a[u],1);//更新线段树 
  for(int i = 0;i < e[u].size();i++){
  	int v=e[u][i];
  	if(v==fa)continue;f[v]=u,de[v]=de[u]+1;
  	dfs(v,u);siz[u]+=siz[v],son[u]=(siz[son[u]]<siz[v]?v:son[u]);
  }
}void dfs1(int u,int fa){
  top[u]=fa;
  if(son[u])dfs1(son[u],fa);
  for(int i = 0;i < e[u].size();i++){
  	int v=e[u][i];
  	if(v==son[u]||v==f[u])continue;
  	dfs1(v,v);
  }
}int lca(int x,int y){
  while(top[x]!=top[y]){
  	if(de[top[x]]<de[top[y]])swap(x,y);
  	x=f[top[x]];
  }return (de[x]<de[y]?x:y);
}int query(int x,int y,int p1,int p2,int l,int r,int k){//这里可能稍微有点恶心，就是点差分的信息维护 
  if(l==r)return l;int mid=(l+r)>>1;
  int val=c[c[x].ls].siz+c[c[y].ls].siz-c[c[p1].ls].siz-c[c[p2].ls].siz;
  if(val>=k)return query(c[x].ls,c[y].ls,c[p1].ls,c[p2].ls,l,mid,k);
  return query(c[x].rs,c[y].rs,c[p1].rs,c[p2].rs,mid+1,r,k-val);
}int k;
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  cin >> n >> m;
  for(int i = 1;i <= n;i++)cin >> a[i],b[i]=a[i];
  sort(b+1,b+1+n);len=unique(b+1,b+1+n)-b-1;
  for(int i = 1;i <= n;i++)a[i]=lower_bound(b+1,b+1+len,a[i])-b;
  for(int i = 1;i < n;i++){
  	cin >> u >> v;
  	e[u].push_back(v);
  	e[v].push_back(u);
  }build(rt[0],1,len);dfs(1,0),dfs1(1,1);int lastans=0;
  for(int i = 1;i <= m;i++){
  	cin >> u >> v >> k;u^=lastans;
  	cout << (lastans=b[query(rt[u],rt[v],rt[lca(u,v)],rt[f[lca(u,v)]],1,len,k)]) << "\n";
  }
  return 0;
}

区间修改

这部分可能会有些难以理解，请读者先掌握基本用法。

很多人初学主席树可能会有一个误区：它不支持区间修改还有区间查询。这个想法我可以很明确的告诉你：它大错特错。现在我们来通过解决一道数据结构题来展开讲解。

首先我们先不考虑可持久化的问题，发现实际上加操作是很好维护的，但推平操作很难维护。所以在这里我们有一个重要观察: $m \le 4$ ，这意味着可以支持对行状态压缩。

我们设 $f_{S,j} = \sum_{i \in S} A_{i,j}$ 。令满状态 $p = 2^m-1$ ，那么我们只需要在意 $f_{p,j}$ 。只有一行的区间推平操作是好维护的，我们只需要在下传标记的同时更新所有与操作行相关的状态 $S$ 即可。比如说我要把第 $i$ 行某个区间修改成 $x$ (这里从 $0$ 开始标号)，对于区间内所有满足 $i \in S$ 的状态，我们直接让 $f_{S,j} = f_{S-i,j} + x$ 。注意这里我们需要从小到大依次更新，并且只需要更新对应的状态。

将上述更新方法沿用至线段树上，我们就做到了用 $2^m-1$ 颗线段树维护推平操作了，至于加操作是同理的，我们只需要处理所有有关的状态对应的线段树。这里建议开一颗线段树，然后维护 $2^m-1$ 个状态，或许会好写一点。

这里提供下传标记的代码：

struct tree{
	int ls,rs,minn[1<<4],tag1[4],tag2[4];
}c[N*10];//线段树结构体 
//c[x]是线段树节点(一个结构体),c[x].tag1[i]表示线段树节点x第i行的修改操作标记,c[x].tag2[i]表示第i行的加操作标记
//c[x].minn[i]表示节点x对应状态i的最小值 
void pushdown1(int x,int id,int y){//维护修改标记,x是标号，id是修改行，y是加权 
	for(int i = 0;i < (1<<m);i++)if(i&(1<<id))c[x].minn[i]=y+c[x].minn[i-(1<<id)];//执行对于有关状态修改,即f{S,i} = f{S-id,i} + y; 
	c[x].tag2[id]=0,c[x].tag1[id]=y;//清除优先级较低的加标记，更新修改标记 
}
void pushdown2(int x,int id,int y){//维护加法标记 
	for(int i = 0;i < (1<<m);i++)if(i&(1<<id))c[x].minn[i]+=y;//执行修改操作 
	c[x].tag2[id]+=y;//修改加标记 
}
void down(int x){//节点下传标记 
	c[x].ls=news(c[x].ls),c[x].rs=news(c[x].rs); // 下传时需要为新版本创建节点
	for(int i = 0;i < m;i++){//枚举行 
		//注意这两个标记的优先级，修改>加 
		if(c[x].tag1[i]!=inf){//下传修改标记 
			pushdown1(c[x].ls,i,c[x].tag1[i]);
			pushdown1(c[x].rs,i,c[x].tag1[i]);
			c[x].tag1[i]=inf;
		}if(c[x].tag2[i]){//下传加标记 
			pushdown2(c[x].ls,i,c[x].tag2[i]);
			pushdown2(c[x].rs,i,c[x].tag2[i]);
			c[x].tag2[i]=0;
		}
	}
}

我们回到可持久化的问题，类比单点修改，区间修改实际上也是在一个版本基础上进行节点信息复制。对需要访问的节点新建版本，否则直接继承版本基础的节点。

然后考虑下传标记的问题，由于我们并不知道每个节点的对应的版本，所以每次我们都需要新建节点，读者可以观察上述代码中 down 函数的第一行。

也就是说，我们在每次区间修改时对访问节点新建，下传标记时新建节点。这样就做到了维护区间修改还有区间查询的问题了，打破了其仅能通过差分进行区间查询的局限性。

这里提供此题的参考代码（std）。若对解决此题感兴趣，可私信作者获取题目或测试数据。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,inf=2e9;
struct Point{
	int ls,rs,minn[1<<4],tag1[4],tag2[4];
}c[N*10];
//线段树结构体 
//c[x]是线段树节点(一个结构体),c[x].tag1[i]表示线段树节点x第i行的修改操作标记,c[x].tag2[i]表示第i行的加操作标记
//c[x].minn[i]表示节点x对应状态i的最小值 
int m,n,q,a[N][4],op,l,r,k,lst,id,rt[N],tot;
int news(int x){
	c[++tot]=c[x];
	return tot;
}//复用某个节点x 
int get(){
	tot++;int x=tot;c[x].ls=c[x].rs=0;
	memset(c[x].minn,0,sizeof(c[x].minn)),memset(c[x].tag2,0,sizeof(c[x].tag2));
	for(int i = 0;i < m;i++)c[x].tag1[i]=inf;
	return tot;
}//直接新建一个空节点x,并对其信息初始化 
void updata(int x){
	for(int i = 0;i < (1<<m);i++)c[x].minn[i]=min(c[c[x].ls].minn[i],c[c[x].rs].minn[i]);	
}
void build(int x,int l,int r){
	for(int i = 0;i < 4;i++)c[x].tag1[i]=inf,c[x].tag2[i]=0;
	if(l==r){
		for(int i = 0;i < (1<<m);i++){
			c[x].minn[i]=0;
			for(int j = 0;j < m;j++)if(i&(1<<j))c[x].minn[i]+=a[l][j];//初始化对应状态 
		}
		return;
	}int mid=(l+r)>>1;c[x].ls=get(),c[x].rs=get();
	build(c[x].ls,l,mid),build(c[x].rs,mid+1,r);updata(x);
}//建树 
void pushdown1(int x,int id,int y){//维护修改标记,x是标号，id是修改行，y是加权 
	for(int i = 0;i < (1<<m);i++)if(i&(1<<id))c[x].minn[i]=y+c[x].minn[i-(1<<id)];//执行对于有关状态修改,即f{S,i} = f{S-id,i} + y; 
	c[x].tag2[id]=0,c[x].tag1[id]=y;//清除优先级较低的加标记，更新修改标记 
}
void pushdown2(int x,int id,int y){//维护加法标记 
	for(int i = 0;i < (1<<m);i++)if(i&(1<<id))c[x].minn[i]+=y;//执行修改操作 
	c[x].tag2[id]+=y;//修改加标记 
}
void down(int x){//节点下传标记 
	c[x].ls=news(c[x].ls),c[x].rs=news(c[x].rs); // 下传时需要为新版本创建节点
	for(int i = 0;i < m;i++){//枚举行 
		//注意这两个标记的优先级，修改>加 
		if(c[x].tag1[i]!=inf){//下传修改标记 
			pushdown1(c[x].ls,i,c[x].tag1[i]);
			pushdown1(c[x].rs,i,c[x].tag1[i]);
			c[x].tag1[i]=inf;
		}if(c[x].tag2[i]){//下传加标记 
			pushdown2(c[x].ls,i,c[x].tag2[i]);
			pushdown2(c[x].rs,i,c[x].tag2[i]);
			c[x].tag2[i]=0;
		}
	}
}
void change(int x,int y,int l,int r,int s,int t,int id,int k){//修改 
	if(l>=s&&r<=t){
		c[x]=c[y];
		pushdown1(x,id,k);
		return;
	}int mid=(l+r)>>1;down(y);//注意由于我们下传的是原版本y，x是新建的复用节点 
	if(s<=mid)c[x].ls=get(),change(c[x].ls,c[y].ls,l,mid,s,t,id,k);
	if(t>mid)c[x].rs=get(),change(c[x].rs,c[y].rs,mid+1,r,s,t,id,k);
	if(!c[x].ls)c[x].ls=c[y].ls;
	if(!c[x].rs)c[x].rs=c[y].rs;
	updata(x);
}
void xg(int x,int y,int l,int r,int s,int t,int id,int k){//加 
	if(l>=s&&r<=t){
		c[x]=c[y];
		pushdown2(x,id,k);
		return;
	}int mid=(l+r)>>1;down(y);//注意由于我们下传的是原版本y，x是新建的复用节点 
	if(s<=mid)c[x].ls=get(),xg(c[x].ls,c[y].ls,l,mid,s,t,id,k);
	if(t>mid)c[x].rs=get(),xg(c[x].rs,c[y].rs,mid+1,r,s,t,id,k);
		if(!c[x].ls)c[x].ls=c[y].ls;
	if(!c[x].rs)c[x].rs=c[y].rs;
	updata(x);
}
int query(int x,int l,int r,int s,int t){
	if(l>=s&&r<=t)return c[x].minn[(1<<m)-1];int mid=(l+r)>>1;down(x);
	if(s>mid)return query(c[x].rs,mid+1,r,s,t);
	else{
		if(t<=mid)return query(c[x].ls,l,mid,s,t);
		return min(query(c[x].ls,l,mid,s,t),query(c[x].rs,mid+1,r,s,t));
	} 
}//查询 
signed main(){ 
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> m >> n >> q;
	for(int i = 0;i < m;i++)for(int j = 1;j <= n;j++)cin >> a[j][i];
	rt[0]=get(),build(rt[0],1,n);
	for(int i = 1;i <= q;i++){
		cin >> lst >> op;
		if(op==1){//对应加操作 
			cin >> id >> l >> r >> k;id--;rt[i]=get();
			xg(rt[i],rt[lst],1,n,l,r,id,k);
		}else if(op==2){//对应修改操作 
			cin >> id >> l >> r >> k;id--;rt[i]=get();
			change(rt[i],rt[lst],1,n,l,r,id,k);
		}else{
			cin >> l >> r;rt[i]=news(rt[lst]);
			cout << query(rt[lst],1,n,l,r) << "\n";
		}
	}
	return 0;
}

很多题目没有让可持久化线段树支持区间修改与查询的原因在于巨大的空间开销，同时这里依然建议多开节点保证正确性。

线段树合并

前置知识：权值线段树，动态开点线段树。

该内容比较简单，读者可以只是稍作了解。
简介和说明如果没有特殊说明，这里默认 $n$ 和值域 $V$ 同阶。

一般而言，权值线段树的操作空间实际上是很小的，因为它只支持修改某些数的出现次数，遇到一些复杂度操作就不行了，比如可重集合并类似的操作。这时候我们就需要引入线段树合并这一概念了。

原理实现
事实上合并两个集合我们有一个非常公式化的做法：启发式合并。只需要每次把较小的集合元素全部加入到另一个集合当中，这样发现对于每个较小集合元素，所在新集合大小至少为原来的两倍，所以一个元素至多被加入 $O(\log n)$ .权值线段树套用启发式合并的方法可以做到 $O(n \log^2 n)$ 。

但事实上这个复杂度并不优秀，如果我们能够快速的维护两个节点内合并的信息那就可以使用线段树合并的技巧做到 $O(n\log n)$ 。

线段树合并的过程实际上非常简单，大概率你能直接推导出如何合并。

假设有两个需要合并的线段树 A 和线段树 B（其中我们把线段树 B 的信息插入至线段树 A），我们考虑同时递归搜索这两棵树并讨论访问到某个节点的情况。

如果 A 树对应节点为空，那么我们直接复用 B 树节点。

如果 B 树对应节点为空，直接返回 A 树对应节点。

综上所述：如果 A 树或 B 树的对应节点为空，那么就直接返回另一颗树上的节点，否则递归到叶子节点时，我们合并两棵树对应节点并返回，并在整个过程中更新维护的信息。

void update(int x){
	//do something
}
int merge(int x,int y,int l,int r){
	if(!x||!y)return x^y;//判断空节点并返回另一颗线段树上的节点，这里x^y等价x+y 
	if(l==r){
		//do something
		return x;
	}int mid=(l+r)>>1;
	c[x].ls=merge(c[x].ls,c[y].ls,l,mid);
	c[x].rs=merge(c[x].rs,c[y].rs,mid+1,r);
	//更新合并后的左右儿子 
	update(x);//更新对应节点 
	return x;//返回合并节点 
}

从刚刚的算法流程中不难看出，一次线段树合并的复杂度是 $O(两颗线段树公共部分)$ 的。由于数的总量为 $O(n \log n)$ 合并量级总会不超过 $O(n \log n)$ 。但是空间常数也是巨大的，此时可以写个可并堆（左偏树）。

下面给出模版题 P4556 基于线段树合并的做法。（本题只需要使用树上差分的技巧，最后树上每个节点合并儿子对应线段树即可）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,u,v,k,de[N],top[N],f[N],son[N],siz[N];
vector <int> e[N];
void dfs(int u,int fa){
	siz[u]=1;
	for(int i = 0;i < e[u].size();i++){
		int v=e[u][i];
		if(v==fa)continue;
		de[v]=de[u]+1,f[v]=u,dfs(v,u);siz[u]+=siz[v];
		son[u]=(siz[v]>siz[son[u]]?v:son[u]);
	}
}
void dfs1(int u,int fa){
	top[u]=fa;
	if(son[u])dfs1(son[u],fa);
	for(int i = 0;i < e[u].size();i++){
		int v=e[u][i];
		if(v==f[u]||v==son[u])continue;
		dfs1(v,v);
	}
}//预处理部分，树上差分 
struct tree{
	int ls,rs,val,id;
}c[N*50];int tot;//巨大的空间常数.... 
void updata(int x){
	if(c[c[x].ls].val<c[c[x].rs].val)c[x].val=c[c[x].rs].val,c[x].id=c[c[x].rs].id; 
	else c[x].val=c[c[x].ls].val,c[x].id=c[c[x].ls].id;//事实上在这里左儿子的值>=右儿子的值，并且左儿子的答案编号一定小于右儿子 
}//维护最优点 
int merge(int x,int y,int l,int r){
	if(!x||!y)return x^y;
	if(l==r){
		c[x].val+=c[y].val;//合并 
		return x;
	}int mid=(l+r)>>1;
	c[x].ls=merge(c[x].ls,c[y].ls,l,mid);
	c[x].rs=merge(c[x].rs,c[y].rs,mid+1,r);updata(x);
	return x;
}
int change(int x,int l,int r,int s,int k){
	if(!x)x=++tot;//单点修改,这里可以使用类似可持久化线段树的写法 
	if(l==r){
		c[x].val+=k;c[x].id=l;
		return x;
	}int mid=(l+r)>>1;
	if(s<=mid)c[x].ls=change(c[x].ls,l,mid,s,k);
	else c[x].rs=change(c[x].rs,mid+1,r,s,k);updata(x);return x;
}int rt[N],ans[N],maxn=1e5;
void dfs2(int u,int fa){
	for(int i = 0;i < e[u].size();i++){
		int v=e[u][i];
		if(v==fa)continue;
		dfs2(v,u);rt[u]=merge(rt[u],rt[v],1,maxn);//合并儿子节点线段树 
	}if(c[rt[u]].val)ans[u]=c[rt[u]].id;
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(de[top[x]]<de[top[y]])swap(x,y);
		x=f[top[x]];
	}return (de[x]<de[y]?x:y);//求lca 
} 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i < n;i++){
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}dfs(1,0),dfs1(1,1);
	for(int i = 1;i <= m;i++){
		cin >> u >> v >> k;
		int lca1=lca(u,v);
		rt[u]=change(rt[u],1,maxn,k,1);
		rt[v]=change(rt[v],1,maxn,k,1);
		rt[lca1]=change(rt[lca1],1,maxn,k,-1);
		rt[f[lca1]]=change(rt[f[lca1]],1,maxn,k,-1);//树上差分 
	}dfs2(1,0);
	for(int i = 1;i <= n;i++)cout << ans[i] << "\n";
	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 132

TQjc
ddd

2026-03-24 来自湖北
24
༺ཌༀ一只猪·郑则则·互关ༀད༻
顶顶顶

2026-03-24 来自广东
24
小白羊（冲1000粉）
666

2026-03-24 来自广东
23
187****3153
1

2026-03-26 来自浙江
22
溯
d

2026-03-25 来自浙江
16
- 海上芙蓉
  回复
  溯
  niubi
  
  2026-03-27 来自江苏
  5
༺ཌༀ一只猪·郑则则·互关ༀད༻
顶顶顶顶

2026-03-26 来自广东
8
睿
d'd'dddd

2026-03-29 来自浙江
7
忠于瑶曦女皇
。。。。。。

2026-03-26 来自浙江
7
睿
ddd

2026-03-29 来自浙江
6
༺དༀ༒小诗晴呀༒ༀཌ༻
555

2026-03-28 来自广东
6
爱吃芝麻小汤圆
1

2026-03-28 来自江苏
3
忠于瑶曦女皇
ddd

2026-03-28 来自浙江
3
忠于瑶曦女皇
ddd

2026-03-28 来自浙江
3
克里斯蒂亚诺罗纳尔多
3

2026-03-28 来自浙江
2
克里斯蒂亚诺罗纳尔多
2

2026-03-28 来自浙江
2
克里斯蒂亚诺罗纳尔多
1

2026-03-28 来自浙江
2
六二大侠
1

2026-03-27 来自浙江
2
prediction
ddd

2026-03-27 来自浙江
2
超赛
来这收藏题单得五罐头

2026-03-27 来自山西
2
- 忠于瑶曦女皇
  回复
  超赛
  那你不是赚了吗，赚的还比我们多，我们收藏1次你加5个
  
  2026-03-28 来自浙江
  2
- 忠于瑶曦女皇
  回复
  超赛
  
  2026-03-28 来自浙江
  2
- 超赛
  回复
  忠于瑶曦女皇
  你收藏拿 1 个，我拿 5 个，都是平台单独发的，你的罐头一点没少。
  我这题单本来就是瞎弄的，能帮你顺便拿个罐头也挺好的，咱们双赢嘛。
  
  2026-03-28 来自山西
  2
忠于瑶曦女皇
做不了一点

2026-03-26 来自浙江
2

前言