概况
背景
线段树，作为一种高级数据结构，其时间复杂度十分优秀。但有一个问题，就是需要的空间非常大，比如，现在给你一个长度为 1e9 的数组，让你在上面建立线段树。这种情况下连数组都开不了，更何况需要四倍空间的线段树呢。动态开点线段树就在这样的情况下出现了。
思路
顾名思义，动态开点线段树就是在需要的时候才建立某个节点，这省去了很多不必要的空间。
比如原来这样一个线段树，共开了 7 个节点
但我们只需要其中一部分，这样就只剩 3 个了。
代码
1.节点建立
点击查看代码
struct node{
int sum,ls,rs;//ls是指左儿子，rs是右儿子，sum是数量和，也可以定义成别的
}t[N<<4];
2.单点加
点击查看代码
void add(int &id,int l,int r,int x,int val){
if(!id)id=++idcnt;//动态开点
if(l==r){
t[id].sum++val;
return;
}
int mid=(l+r)>>1;
if(x<=mid)add(t[id].ls,l,mid,x,val);
else add(t[id].rs,mid+1,r,x,val);
t[id].sum=t[t[id].ls].sum+t[t[id].rs].sum;
}
其他的都和普通线段树差不多，区间加的时候注意动态开店即可。
标签：int,线段,id,sum,动态,节点 From： https://www.cnblogs.com/WDY-Hodur/p/18582655