原题链接
线段树第一弹 放个板子题
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<queue> #include<vector> #include<climits> #include<string> #include<cstdlib> #include<ctime> #define MOD 1000000007 #define LL long long using namespace std; struct nico { int lazy,l,r,len; LL sum; }point[800005]; int n,a[200005],d,b,c,q,mark,i; LL t; void build(int lef,int rig,int p) { int mid; point[p].l=lef; point[p].r=rig; point[p].len=rig-lef+1; if(lef==rig) { point[p].sum=a[lef]; return; } mid=(lef+rig)>>1; build(lef,mid,p<<1); build(mid+1,rig,(p<<1)+1); point[p].sum=point[p<<1].sum+point[(p<<1)+1].sum; } void pushdown(int p) { point[p<<1].lazy+=point[p].lazy; point[(p<<1)+1].lazy+=point[p].lazy; point[p<<1].sum+=1ll*point[p].lazy*point[p<<1].len; point[(p<<1)+1].sum+=1ll*point[p].lazy*point[(p<<1)+1].len; point[p].lazy=0; } void add(int al,int ar,int x,int p) { int mid,lef,rig; lef=point[p].l; rig=point[p].r; if(ar<lef||al>rig) return; if(al==lef&&ar==rig) { point[p].lazy+=x; point[p].sum+=1ll*x*point[p].len; return; } mid=(lef+rig)>>1; if(point[p].lazy>0) pushdown(p); if(ar<=mid) add(al,ar,x,p<<1); if(al>mid) add(al,ar,x,(p<<1)+1); if(al<=mid&&ar>mid) { add(al,mid,x,p<<1); add(mid+1,ar,x,(p<<1)+1); } point[p].sum=point[p<<1].sum+point[(p<<1)+1].sum; } LL search(int al,int ar,int l,int r,int p) { int mid; if(ar<l||al>r) return 0; if(al==l&&ar==r) return point[p].sum; mid=(l+r)>>1; if(point[p].lazy>0) pushdown(p); if(ar<=mid) return search(al,ar,l,mid,p<<1); if(al>mid) return search(al,ar,mid+1,r,(p<<1)+1); if(al<=mid&&ar>mid) return search(al,mid,l,mid,p<<1)+search(mid+1,ar,mid+1,r,(p<<1)+1); } int main() { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); build(1,n,1); scanf("%d",&q); for(i=1;i<=q;i++) { scanf("%d",&mark); if(mark==1) { scanf("%d%d%d",&d,&b,&c); add(d,b,c,1); } if(mark==2) { scanf("%d%d",&d,&b); t=search(d,b,1,n,1); printf("%lld\n",t); } } return 0; }