线段树1

``` #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int n,m; int x,y,k; int v[500001],Lazy[500001]; long long s[1000001]; void pushdown(int o,int left,int right) { if(!Lazy[o])return; int mid=(right+left)>>1; if(left==right)return; s[o<<1]+=Lazy[o]*(mid-left+1); Lazy[o<<1]+=Lazy[o]; s[o<<1|1]+=Lazy[o]*(right-mid); Lazy[o<<1|1]+=Lazy[o]; Lazy[o]=0; } long long search(int o,int left,int right) { pushdown(o,left,right); if(x<=left&&y>=right)return s[o]; long long sum=0; int mid=(left+right)>>1; if(x<=mid) sum+=search(o<<1,left,mid); if(y>mid) sum+=search(o<<1|1,mid+1,right); return sum; } void change(int o,int left,int right) { pushdown(o,left,right); if(x<=left&&y>=right) { s[o]+=k*(right-left+1); Lazy[o]=k; return; } int mid=(left+right)>>1; if(x<=mid)change(o<<1,left,mid); if(y>mid)change(o<<1|1,mid+1,right); s[o]=s[o<<1]+s[o<<1|1]; } void build(int o,int left,int right) { if(left==right){ s[o]=v[left]; return; } int mid=(left+right)>>1; build(o<<1,left,mid); build(o<<1|1,mid+1,right); s[o]=s[o<<1]+s[o<<1|1]; } int main() { int a; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&v[i]); } build(1,1,n); for(int i=1;i<=m;i++) { scanf("%d",&a); if(a==1) { scanf("%d%d%d",&x,&y,&k); change(1,1,n); } if(a==2) { scanf("%d%d",&x,&y); printf("%lld\n",search(1,1,n)); } } return 0; } ```