点击查看代码
#include<bits/stdc++.h>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int N=1e6+12000;
struct node{int l,r,num;int ma,mi;
}tr[N<<2];
int a[N];
int n,m;
string str;
int ans=0;
int from,to;
void build(int id,int l,int r){tr[id].l=l;tr[id].r=r;if(l==r){tr[id].num=a[l];tr[id].ma=a[l];tr[id].mi=a[l];return;}int mid=(l+r)/2;build(lson,l,mid);build(rson,mid+1,r);tr[id].num=tr[lson].num+tr[rson].num;tr[id].ma=max(tr[lson].ma,tr[rson].ma);tr[id].mi=min(tr[lson].mi,tr[rson].mi);
}
void update(int id,int x,int ad){if(tr[id].l==tr[id].r){tr[id].num+=ad;tr[id].ma+=ad;tr[id].mi+=ad;return;}int mid=(tr[id].l+tr[id].r)/2;if(x<=mid) update(lson,x,ad);else update(rson,x,ad);tr[id].num=tr[lson].num+tr[rson].num; tr[id].ma=max(tr[lson].ma,tr[rson].ma);tr[id].mi=min(tr[lson].mi,tr[rson].mi);
}
int getsum(int id,int l,int r){if(r>=tr[id].r&&l<=tr[id].l){return tr[id].num;}int mid=(tr[id].l+tr[id].r)/2;if(mid<l) return getsum(rson,l,r);else if(mid>=r) return getsum(lson,l,r);else return getsum(lson,l,mid)+getsum(rson,mid+1,r);
}
int getmax(int id,int l,int r){if(r>=tr[id].r&&l<=tr[id].l){return tr[id].ma;}int maxn=0;int mid=(tr[id].r+tr[id].l)/2;if(mid<l) maxn=max(maxn,getmax(rson,l,r));else if(mid>=r) maxn=max(maxn,getmax(lson,l,r));else maxn=max({maxn,getmax(lson,l,mid),getmax(rson,mid+1,r)});return maxn;
}
int getmin(int id,int l,int r){if(r>=tr[id].r&&l<=tr[id].l){return tr[id].ma;}int minn=0x7fffffff;int mid=(tr[id].l+tr[id].r)/2;if(mid<l) minn=min(minn,getmin(rson,l,r));else if(mid>=r) minn=min(minn,getmin(lson,l,r));else minn=min({minn,getmin(lson,l,mid),getmin(rson,mid+1,r)});return minn;
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}cin>>m;if(n) build(1,1,n);for(int i=1;i<=m;i++){cin>>str>>from>>to;if(str=="ADD"){update(1,from,to);}else{cout<<getsum(1,from,to)<<endl;}}
}
几个注意点
1.更新和建树跑到叶子时要return
if(tr[id].l==tr[id].r){tr[id].num+=ad;tr[id].ma+=ad;tr[id].mi+=ad;return;}
if(l==r){tr[id].num=a[l];tr[id].ma=a[l];tr[id].mi=a[l];return;}
2.关于取等
if(mid<l) return getsum(rs,l,r);else if(mid>=r) return getsum(ls,l,r);else return getsum(ls,l,mid)+getsum(rs,mid+1,r);
分别对应以上三行代码，因为我们是将l到mid定为lson，mid+1到r定为rson,所以查询的左边界要大于mid才能完全在右区间，而右边界仅需小于等于
3.区间处理（lazy标记）
点击查看代码
#include<bits/stdc++.h>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int N=1e6+1200;
int a[N];
int n,m;
struct node{int l,r,lazy,num;
}tr[N<<2];
void build(int id,int l,int r){tr[id].l=l;tr[id].r=r;if(l==r){tr[id].num=a[l];return;}int mid=(l+r)/2;build(lson,l,mid);build(rson,mid+1,r);tr[id].num=tr[lson].num+tr[rson].num;
}
void pushup(int id){tr[lson].lazy+=tr[id].lazy;tr[rson].lazy+=tr[id].lazy;tr[lson].num+=(tr[lson].r-tr[lson].l+1)*tr[id].lazy;tr[rson].num+=(tr[rson].r-tr[rson].l+1)*tr[id].lazy;tr[id].lazy=0;
}
void update(int id,int l,int r,int ad){if(l>tr[id].r||r<tr[id].l){return;}if(tr[id].r<=r&&tr[id].l>=l){tr[id].num+=ad*(tr[id].r-tr[id].l+1);tr[id].lazy+=ad;return;}int mid=(tr[id].l+tr[id].r)/2;pushup(id);update(lson,l,r,ad);update(rson,l,r,ad);tr[id].num=tr[lson].num+tr[rson].num;
}
int getsum(int id,int l,int r){if(l>tr[id].r||r<tr[id].l){return 0;}if(tr[id].r<=r&&tr[id].l>=l){return tr[id].num;}int mid=(tr[id].l+tr[id].r)/2;pushup(id);return getsum(lson,l,mid)+getsum(rson,mid+1,r);
}
int main(){string str;int from,to,w;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}build(1,1,n);cin>>m;for(int i=1;i<=m;i++){cin>>str;if(str=="SUM"){cin>>from>>to;cout<<getsum(1,from,to)<<endl;}else {cin>>from>>to>>w;update(1,from,to,w);}}
}void pushup(int id){tr[lson].lazy+=tr[id].lazy;tr[rson].lazy+=tr[id].lazy;//处理id以及它的子树对应的总和，将子树以及它的子子树的处理先放置一边tr[lson].num+=(tr[lson].r-tr[lson].l+1)*tr[id].lazy;tr[rson].num+=(tr[rson].r-tr[rson].l+1)*tr[id].lazy;tr[id].lazy=0;//处理完清零
}
（画的不是太好，但基本是这么个意思）
