详解动态开点线段树
线段树动态开点
前置知识：线段树。
例题
CF915E Physical Education Lessons
题目描述
题意：
Alex高中毕业了，他现在是大学新生。虽然他学习编程，但他还是要上体育课，这对他来说完全是一个意外。快要期末了，但是不幸的Alex的体育学分还是零蛋！
Alex可不希望被开除，他想知道到期末还有多少天的工作日，这样他就能在这些日子里修体育学分。但是在这里计算工作日可不是件容易的事情：
从现在到学期结束还有
n 天(从1 到n 编号)，他们一开始都是工作日。接下来学校的工作人员会依次发出q 个指令，每个指令可以用三个参数l,r,k 描述：
如果
k=1 ，那么从l 到r （包含端点）的所有日子都变成非工作日。如果
k=2 ，那么从l 到r （包含端点）的所有日子都变成工作日。帮助Alex统计每个指令下发后，剩余的工作日天数。
输入格式
第一行一个整数
n ，第二行一个整数q (1\le n\le 10^9,\;1\le q\le 3\cdot 10^5) ，分别是剩余的天数和指令的个数。接下来
q 行，第i 行有3 个整数l_i,r_i,k_i ，描述第i 个指令(1\le l_i,r_i\le n,\;1\le k\le 2) 。输出格式
输出
q 行，第i 行表示第i 个指令被下发后剩余的工作日天数。输入输出样例 #1
输入 #1
4 6 1 2 1 3 4 1 2 3 2 1 3 2 2 4 1 1 4 2输出 #1
2 0 2 3 1 4
因为本题中
思路
动态开点线段树与普通线段树的区别是它并没有在一开始时就将线段树的每一个结点建出来，而是随着操作将需要的点开出来。
假如我们维护一个长度为 4 的区间的和。
用一张形象的图：
注：图中灰色的部分表示没有开点的部分
这是一个还没有开点的线段树。
如果我们将区间中的第 3 个数修改为 2。
第一步（在根节点root）：
因为根节点是第一个遍历的节点，所以根节点的编号为 1，将根节点表示的值（[1,4]的值）加上 2（原因后面会说）。
第二步（遍历到表示[3,4]节点）：
因为这个节点是第二个遍历的节点，所以该节点的编号为 2，将该节点表示的值（[3,4]的值）加上 2（原因后面会说）。
第三步（遍历到表示[3,3]的叶子节点）：
因为这个节点是第三个遍历的节点，所以该节点的编号为 3，将该节点表示的值（[3,4]的值）加上 2，此时发现前面遍历到的所有节点的值都包括该叶子节点，这就是为什么要将前面的所有节点的值加 2 的原因。
到此，一个修改操作就完成了。
修改部分代码
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时如果该节点没有左右儿子，需要新开节点表示儿子。
完整代码
#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;
}总结
在做题时，其实对于这类数据范围较大的题目一般使用离散化处理，但是在可持久化线段树中还需要使用动态开点，所以线段树动态开点也是一项必须掌握的知识点。