线段树区间加区间查询
记得要开long long
#include<iostream> #include<fstream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; int n,m; struct data{ int l,r; long long s,add; }t[400003]; void pushup(int k){ t[k].s=t[k<<1].s+t[k<<1|1].s; } void pushdown(int k){ if(t[k].l==t[k].r){ return; } if(t[k].add){ t[k<<1].add+=t[k].add; t[k<<1|1].add+=t[k].add; t[k<<1].s+=t[k].add*(t[k<<1].r-t[k<<1].l+1); t[k<<1|1].s+=t[k].add*(t[k<<1|1].r-t[k<<1|1].l+1); t[k].add=0; } } void build(int k,int l,int r){ t[k].l=l,t[k].r=r; if(l==r){ cin>>t[k].s; return; } int mid=(l+r)/2; build(k<<1,l,mid); build(k<<1|1,mid+1,r); pushup(k); } void add(int k,int x,int y,int v){ pushdown(k); int l=t[k].l,r=t[k].r,sum=r-l+1; if(l==x&&r==y){ t[k].add+=v; t[k].s+=(long long)sum*v; return; } int mid=(l+r)>>1; if(mid>=y){ add(k<<1,x,y,v); }else if(mid<x){ add(k<<1|1,x,y,v); }else{ add(k<<1,x,mid,v); add(k<<1|1,mid+1,y,v); } pushup(k); } long long que(int k,int x,int y){ pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&r==y){ return t[k].s; } int mid=(l+r)>>1; if(mid>=y){ return que(k<<1,x,y); }else if(mid<x){ return que(k<<1|1,x,y); }else{ return que(k<<1,x,mid)+que(k<<1|1,mid+1,y); } } int main(){ cin>>n>>m; build(1,1,n); for(int i=1;i<=m;i++){ int x,y,z; char ch[10]; cin>>ch; if(ch[0]=='Q'){ cin>>x>>y; cout<<que(1,x,y)<<endl; }else{ cin>>x>>y>>z; add(1,x,y,z); } } return 0; } /* in: 10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4 out: 4 55 9 15 */