专栏文章

详解动态开点线段树

BBennyT
算法·理论参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@miofcayr
此快照首次捕获于
2025/12/02 18:17
3 个月前
此快照最后确认于
2025/12/02 18:17
3 个月前
查看原文

线段树动态开点

前置知识：线段树。

例题

CF915E Physical Education Lessons

题目描述

题意：

Alex高中毕业了，他现在是大学新生。虽然他学习编程，但他还是要上体育课，这对他来说完全是一个意外。快要期末了，但是不幸的Alex的体育学分还是零蛋！
Alex可不希望被开除，他想知道到期末还有多少天的工作日，这样他就能在这些日子里修体育学分。但是在这里计算工作日可不是件容易的事情：
从现在到学期结束还有 nn 天(从 11 到 nn 编号)，他们一开始都是工作日。接下来学校的工作人员会依次发出 qq 个指令，每个指令可以用三个参数 l,r,kl,r,k 描述：
  • 如果 k=1k=1，那么从 ll 到 rr （包含端点）的所有日子都变成非工作日。
  • 如果 k=2k=2，那么从 ll 到 rr （包含端点）的所有日子都变成工作日。
帮助Alex统计每个指令下发后，剩余的工作日天数。

输入格式

第一行一个整数 nn，第二行一个整数 qq (1≤n≤109,  1≤q≤3⋅105)(1\le n\le 10^9,\;1\le q\le 3\cdot 10^5)，分别是剩余的天数和指令的个数。
接下来 qq 行，第 ii 行有 33 个整数 li,ri,kil_i,r_i,k_i，描述第 ii 个指令 (1≤li,ri≤n,  1≤k≤2)(1\le l_i,r_i\le n,\;1\le k\le 2)。

输出格式

输出 qq 行，第 ii 行表示第 ii 个指令被下发后剩余的工作日天数。

输入输出样例 #1

输入 #1

CPP
4
6
1 2 1
3 4 1
2 3 2
1 3 2
2 4 1
1 4 2

输出 #1

CPP
2
0
2
3
1
4
因为本题中 nn 的数据范围过大，无法直接使用线段树，这是就需要动态开点线段树了。

思路

动态开点线段树与普通线段树的区别是它并没有在一开始时就将线段树的每一个结点建出来，而是随着操作将需要的点开出来。
假如我们维护一个长度为 4 的区间的和。
用一张形象的图：
注：图中灰色的部分表示没有开点的部分
这是一个还没有开点的线段树。
如果我们将区间中的第 3 个数修改为 2。
第一步（在根节点root）：
因为根节点是第一个遍历的节点，所以根节点的编号为 1，将根节点表示的值（[1,4]的值）加上 2（原因后面会说）。
第二步（遍历到表示[3,4]节点）：
因为这个节点是第二个遍历的节点，所以该节点的编号为 2，将该节点表示的值（[3,4]的值）加上 2（原因后面会说）。
第三步（遍历到表示[3,3]的叶子节点）：
因为这个节点是第三个遍历的节点，所以该节点的编号为 3，将该节点表示的值（[3,4]的值）加上 2，此时发现前面遍历到的所有节点的值都包括该叶子节点，这就是为什么要将前面的所有节点的值加 2 的原因。
到此，一个修改操作就完成了。

修改部分代码

CPP
void change(int &p,int l,int r,int x,int y,int k){
    if(!p){//如果该节点还没有开
        tr[p=++id]={0,0,r-l+1,-1};
    }
    if(l>=x&&r<=y){
    	k--;
    	k^=1;
        tr[p].c=k*(r-l+1);
        tr[p].la=k;
        return ;
    }
    pushdown(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)change(tr[p].ls,l,mid,x,y,k);
    if(y>mid)change(tr[p].rs,mid+1,r,x,y,k);
    pushup(p);
}
其他部分就和普通线段树相差不大了
另外需要注意的是，在pushdown时如果该节点没有左右儿子，需要新开节点表示儿子。

完整代码

CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,id,rt;
struct N{
    int ls,rs,c,la;
}tr[15000010];
void pushup(int p){
    tr[p].c=tr[tr[p].ls].c+tr[tr[p].rs].c;
}
void pushdown(int p,int l,int r){
    if(tr[p].la==-1)return ;
    if(!tr[p].ls){
        tr[tr[p].ls=++id]={0,0,0,-1};
    }
    if(!tr[p].rs){
        tr[tr[p].rs=++id]={0,0,0,-1};
    }
    int mid=(l+r)>>1;
    tr[tr[p].ls].c=tr[p].la*(mid-l+1);
    tr[tr[p].ls].la=tr[p].la;
    tr[tr[p].rs].c=tr[p].la*(r-mid);
    tr[tr[p].rs].la=tr[p].la;
    tr[p].la=-1;
}
void change(int &p,int l,int r,int x,int y,int k){
    if(!p){
        tr[p=++id]={0,0,r-l+1,-1};
    }
    if(l>=x&&r<=y){
    	k--;
    	k^=1;
        tr[p].c=k*(r-l+1);
        tr[p].la=k;
        return ;
    }
    pushdown(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)change(tr[p].ls,l,mid,x,y,k);
    if(y>mid)change(tr[p].rs,mid+1,r,x,y,k);
    pushup(p);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    while(q--){
        int k,x,y;
        cin>>x>>y>>k;
        change(rt,1,n,x,y,k);
        cout<<n-tr[rt].c<<'\n';
    }
    return 0;
}

总结

在做题时，其实对于这类数据范围较大的题目一般使用离散化处理，但是在可持久化线段树中还需要使用动态开点，所以线段树动态开点也是一项必须掌握的知识点。

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...