什么是动态开点

就是一种线段树实现的一种技巧。

具体来说，就是我们发现在线段树中，有很多对于答案还没有贡献的空节点，如果采用堆式存储法，会浪费很多没有必要的空间来存空节点，而这些节点有可能到最后也不会用到，这就是一种实质上的浪费。

当然，只开几棵线段树其实并不会影响那么多，动态开点也有点繁琐，没有必要为了一点空间去使用动态开点。

但是，如果你开了

N

棵线段树，每棵线段树只有大约寥寥

\log_2 n

个节点是对答案产生贡献的有效节点，那么动态开点就是必要的了。

作者犯糖了，放了一道重剖的题目

学习单纯的动态开点请以这道题为例

以P3313 [SDOI2014] 旅行为例做一个讲解

P3313 [SDOI2014] 旅行

题目描述

S 国有

N

个城市，编号从

1

到

N

。城市间用

N-1

条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。

为了方便，我们用不同的正整数代表各种宗教，S 国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S 国为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。

在 S 国的历史上常会发生以下几种事件：

CC x c：城市 $x$ 的居民全体改信了 $c$ 教；
CW x w：城市 $x$ 的评级调整为 $w$ ；
QS x y：一位旅行者从城市 $x$ 出发，到城市 $y$ ，并记下了途中留宿过的城市的评级总和；
QM x y：一位旅行者从城市 $x$ 出发，到城市 $y$ ，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

输入格式

输入的第一行包含整数

N,Q

依次表示城市数和事件数。

接下来

N

行，第

i+1

行两个整数

W_i,C_i

依次表示记录开始之前，城市

i

的评级和信仰。

接下来

N-1

行每行两个整数

x,y

表示一条双向道路。

接下来

Q

行，每行一个操作，格式如上所述。

输出格式

对每个 QS 和 QM 事件，输出一行，表示旅行者记下的数字。

输入输出样例 #1

输入 #1

CPP

输出 #1

CPP

说明/提示

对于

100\%

的数据，

N,Q \leq10^5,C \leq10^5

数据保证对所有 QS 和 QM 事件，起点和终点城市的信仰相同；在任意时刻，城市的评级总是不大于

10^4

的正整数，且宗教值不大于

C

。

思路

这道题目乍一看十分的逆天，但是仔细分析来看，只要对于每一种宗教都建一棵线段树，维护信仰

c

宗教的城市的评级，再修改，查询就好了。

好个啥。。。你的空间不炸了？一共可能用

c

棵线段树，每个线段树

\Theta(4\times n)

的空间，看看

c

和

n

你不炸了？

所以我们就需要动态开点，如果每棵线段树只需要

\Theta(\log_2 n)

个节点，那么一共也只需要

\Theta(c\times \log_2 n)

个节点，空间一下子就少了很多，也就可以开

c

棵线段树了。

不过还有一个问题，改教（操作CC）要怎么处理？

也很简单，只要在城市

x

原本属于的那棵线段树那里将

x

的评级改为 0 ，再将第

c

棵线段树里单点修改城市

x

的评级为

x

的评级即可（没有点就动态开）。

Talk Is CHEAP,Show you My Code

CPP

#include<bits/stdc++.h>
#define int long long
#define bug cout<<"BUG\n"
#define V vector
using namespace std;
const int N=2e5+10;
const int INF=1e9+10;
int root[N],idx=0;
struct node{
	int ls,rs,w,maxn;
}a[N<<4];
inline int ls(int x){return a[x].ls;}
inline int rs(int x){return a[x].rs;}
void push_up(int x){
	a[x].w=a[ls(x)].w+a[rs(x)].w;
	a[x].maxn=max(a[ls(x)].maxn,a[rs(x)].maxn);
}
void update(int &x,int l,int r,int pos,int w){
	if(!x) x=++idx;//这里和主席树不同
	a[x].maxn=max(a[x].maxn,w);a[x].w+=w;
	if(l==r)return;
	int mid=l+r>>1;
	if(pos<=mid) update(a[x].ls,l,mid,pos,w);
	else update(a[x].rs,mid+1,r,pos,w);
}
void remove(int &x,int l,int r,int pos){
	if(l==r){
		a[x].maxn=a[x].w=0;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid) remove(a[x].ls,l,mid,pos);
	else remove(a[x].rs,mid+1,r,pos);
	push_up(x);
}
int query_sum(int x,int l,int r,int L,int R){
	if(l>R||r<L) return 0;
	if(l>=L&&r<=R) return a[x].w;
	int mid=l+r>>1;
	return query_sum(a[x].ls,l,mid,L,R)+query_sum(a[x].rs,mid+1,r,L,R);
}
int query_max(int x,int l,int r,int L,int R){
	if(l>R||r<L) return -INF;
	if(l>=L&&r<=R) return a[x].maxn;
	int mid=l+r>>1;
	return max(query_max(a[x].ls,l,mid,L,R),query_max(a[x].rs,mid+1,r,L,R));
}
V<V<int> >e;
V<int>siz,son,fa,dep,id,xy/*信仰*/,top;
int cnt=0;
void dfs1(int u,int fat){
	fa[u]=fat;
	dep[u]=dep[fat]+1;
	siz[u]=1;
	for(int v:e[u]){
		if(v==fat)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(!son[u]||siz[son[u]]<siz[v]) son[u]=v;
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	id[u]=++cnt;
	if(!son[u])return;
	dfs2(son[u],tp);
	for(int v:e[u]){
		if(v==son[u]||v==fa[u])continue;
		dfs2(v,v);
	}
}
int n;
int query_range_sum(int u,int v,int zj){
	int ans=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ans+=query_sum(root[zj],1,n,id[top[u]],id[u]);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	ans+=query_sum(root[zj],1,n,id[u],id[v]);
	return ans;
}
int query_range_max(int u,int v,int zj){
	int ans=-INF;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ans=max(ans,query_max(root[zj],1,n,id[top[u]],id[u]));
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	ans=max(ans,query_max(root[zj],1,n,id[u],id[v]));
	return ans;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int q;cin>>n>>q;
	e.resize(n+1);fa.resize(n+1);dep.resize(n+1);
	siz.resize(n+1);son.resize(n+1);id.resize(n+1);
	xy.resize(n+1);top.resize(n+1);
	V<int>pj(n+1),zj(n+1);
	for(int i=1;i<=n;i++) cin>>pj[i]>>zj[i];
	for(int i=1,a,b;i<n;i++){
		cin>>a>>b;
		e[a].push_back(b);e[b].push_back(a);
	}
	dfs1(1,0);dfs2(1,1);
	for(int i=1;i<=n;i++) update(root[zj[i]],1,n,id[i],pj[i]);
	while(q--){
		string op;
		int x,y;
		cin>>op>>x>>y;
		if(op=="CC"){
			remove(root[zj[x]],1,n,id[x]);
			update(root[y],1,n,id[x],pj[x]);
			zj[x]=y;
		}
		if(op=="CW"){
			remove(root[zj[x]],1,n,id[x]);
			update(root[zj[x]],1,n,id[x],y);
			pj[x]=y;
		}
		if(op=="QS") cout<<query_range_sum(x,y,zj[x])<<"\n";
		if(op=="QM") cout<<query_range_max(x,y,zj[x])<<"\n";
	}
	return 0;
}

本题的评级是

\color{blue}{蓝}

，实则已经是

\color{skyblue}{浅蓝}

了，都是重剖模板撑起来的评级，动态开点最多有个

\color{green}{绿}

，所以本题还是十分简单的。

比如这道就是一道

\color{green}{绿}

的思路。

后记

2025.10.16 updated，我实在是太唐了，不小心放了一道重剖，thxMyself

2025.10.17 updated，修改了一处笔误,thx一个喜欢打aqtw的人

动态开点真是个好东西

文章操作