动态开点真是个好东西

· · 个人记录

什么是动态开点

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

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

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

但是，如果你开了 N 棵线段树，每棵线段树只有大约寥寥 \log_2 n 个节点是对答案产生贡献的有效节点，那么动态开点就是必要的了。

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

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

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

P3313 [SDOI2014] 旅行

题目描述

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

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

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

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

输入格式

输入的第一行包含整数 N,Q 依次表示城市数和事件数。

接下来 N 行，第 i+1 行两个整数 W_i,C_i 依次表示记录开始之前，城市 i 的评级和信仰。

接下来 N-1 行每行两个整数 x,y 表示一条双向道路。

接下来 Q 行，每行一个操作，格式如上所述。

输出格式

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

输入输出样例 #1

输入 #1

5 6
3 1
2 3
1 2
3 3
5 1
1 2
1 3
3 4
3 5
QS 1 5
CC 3 1
QS 1 5
CW 3 3
QS 1 5
QM 2 4

输出 #1

8
9
11
3

说明/提示

对于 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

#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的人