首先是动态树，以数列操作为例
点击查看代码
#include<bits/stdc++.h>
#define lson tr[id].l
#define rson tr[id].r
using namespace std;
const int N=1e6+20;
int a[N];
struct node{
int l,r,sum;
}tr[N<<2];
int n,m;
int num;
int rt;
void update(int &id,int l,int r,int x,int ad){
if(id==0) id=++num;//动态开点
if(l==r){//递归到叶子
tr[id].sum+=ad;return;
}
int mid=(l+r)/2;
if(x<=mid) update(lson,l,mid,x,ad);
else update(rson,mid+1,r,x,ad);
tr[id].sum=tr[lson].sum+tr[rson].sum;
}
//int query(int id,int l,int r,int L,int R){
// if(id==0) return 0;
// if(l>=L&&r<=R) return tr[id].sum;
// int ans=0;
// int mid=(l+r)/2;
// if(L<=mid) ans+=query(lson,l,mid,L,R);
// if(R>mid) ans+=query(rson,mid+1,r,L,R);
// return ans;
//}
//这样也可以
//int query(int id,int l,int r,int L,int R){
// if(id==0) return 0;
// if(l>=L&&r<=R) return tr[id].sum;
// int mid=(l+r)/2;
// if(R<mid) return query(lson,l,mid,L,R);
// else if(L>mid) return query(rson,mid+1,r,L,R);
// else return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
//}一样
int query(int id,int l,int r,int L,int R){
if(l>R||r<L)return 0;
if(id==0) return 0;
if(l>=L&&r<=R) return tr[id].sum;
int mid=(l+r)/2;
return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
}
int main(){
int from,to;
string str;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
update(rt,1,n,i,a[i]);
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>str>>from>>to;
if(str=="ADD"){
update(rt,1,n,from,to);
}
else{
cout<<query(rt,1,n,from,to)<<endl;
}
}
}
4
1 4 2 3
3
SUM 1 3
ADD 2 50
SUM 2 3
因为引用符的使用，会在左右儿子更新完后给根赋上左右儿子的编号
void update(int &id,int l,int r,int x,int ad){
if(id==0) id=++num;
if(l==r){
tr[id].sum+=ad;return;
}
int mid=(l+r)/2;
if(x<=mid) update(lson,l,mid,x,ad);
else update(rson,mid+1,r,x,ad);
tr[id].sum=tr[lson].sum+tr[rson].sum;
}
并且要引用边界，因为在普通线段树中，左右儿子的编号是固定的，树记得是左右边界，但在动态的线段树中，树记得是左右儿子（虽然左右儿子管辖的是l到mid和mid+1到r，但在比较区间时无法比较），所以要额外加上边界
此外，对于这个题来说，因为是一棵树，所以它的根节点编号恒为1
然后是权值线段树
这时候每个叶子代表的就是一个桶，记录每个数出现的次数，它们的根就是一个大桶，记录范围内出现数的次数总和
void update(int &rt,int l,int r,int x,int ad){
if(rt==0) rt=++num;
if(l==r){
tr[rt].num=ad;
tr[rt].cnt++;
return;
}
int mid=(l+r)/2;
if(x<=mid) update(lson,l,mid,x,ad);
else update(rson,mid+1,r,x,ad);
tr[rt].cnt=tr[lson].cnt+tr[rson].cnt;
}
有一个问题：动态的线段树怎么求区间和以及区间的修改，还是根本实现不了
标签：rt,int,tr,线段,扩展,mid,query,id From： https://www.cnblogs.com/PeppaEvenPigShiGeNiuBDePig/p/18187456