有点标题党,实际是想要评价线段树模板,是不是够简洁(我是手残,打字打不快)清晰
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1014514;
int n,m,a[maxn],tree[maxn*4],tag[maxn*4];
int ls(int x){
return x*2;
}
int rs(int x){
return x*2+1;
}
void pushup(int x){
tree[x]=tree[ls(x)]+tree[rs(x)];
}
void build(int id,int l,int r){
tag[id]=0;
if(l==r){
tree[id]=a[l];
return;
}
int mid=(l+r)/2;
build(ls(id),l,mid);
build(rs(id),mid+1,r);
pushup(id);
}
void add(int id,int l,int r,int k){
tag[id]+=k;
tree[id]+=k*(r-l+1);
}
void push_down(int id,int l,int r){
int mid=(l+r)/2;
add(ls(id),l,mid,tag[id]);
add(rs(id),mid+1,r,tag[id]);
tag[id]=0;
}
void update(int nl,int nr,int l,int r,int id,int k){
if(l>=nl&&r<=nr){
tree[id]+=k*(r-l+1);
tag[id]+=k;
return;
}
push_down(id,l,r);
int mid=(l+r)/2;
if(nl<=mid)update(nl,nr,l,mid,ls(id),k);
if(nr>mid)update(nl,nr,mid+1,r,rs(id),k);
pushup(id);
}
int query(int nl,int nr,int l,int r,int id){
int sum=0;
if(l>=nl&&r<=nr)return tree[id];
int mid=(l+r)/2;
push_down(id,l,r);
if(nl<=mid)sum+=query(nl,nr,l,mid,ls(id));
if(nr>mid)sum+=query(nl,nr,mid+1,r,rs(id));
return sum;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++){
int op;
cin>>op;
if(op==1){
int l,r,k;
cin>>l>>r>>k;
update(l,r,1,n,1,k);
}
if(op==2){
int l,r;
cin>>l>>r;
cout<<query(l,r,1,n,1)<<"\n";
}
}
return 0;
}
另外,我每天都打一遍线段树有助于记忆吗?