思路：这道题出发点就是为了练习线段树的板子题，但是我另外用了分块算法做了这道题，后面也会贴出相应的线段树解法。
分块算法：
#include<set> #include<queue> #include<vector> #include<string> #include<math.h> #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; #define maxn 200005 #define ll long long ll sum[maxn],mark[maxn]; int n,m,a[maxn],sq,size[maxn]; int st[maxn],ed[maxn],bel[maxn]; void init(int n){ sq=sqrt(n); for(int i=1;i<=sq;i++){ st[i]=n/sq*(i-1)+1; ed[i]=n/sq*i; } ed[sq]=n; for(int i=1;i<=sq;i++){ for(int j=st[i];j<=ed[i];j++) bel[j]=i; size[i]=ed[i]-st[i]+1; } } void update(int l,int r,int x){ if(bel[l]==bel[r]){ for(int i=l;i<=r;i++){ a[i]+=x; sum[bel[i]]+=x; } } else{ for(int i=l;i<=ed[bel[l]];i++){ a[i]+=x; sum[bel[i]]+=x; } for(int i=st[bel[r]];i<=r;i++){ a[i]+=x; sum[bel[i]]+=x; } for(int i=bel[l]+1;i<bel[r];i++) mark[i]+=x; } } ll query(int l,int r){ ll res=0; if(bel[l]==bel[r]){ for(int i=l;i<=r;i++) res+=a[i]+mark[bel[i]]; } else{ for(int i=l;i<=ed[bel[l]];i++) res+=a[i]+mark[bel[i]]; for(int i=st[bel[r]];i<=r;i++) res+=a[i]+mark[bel[i]]; for(int i=bel[l]+1;i<bel[r];i++) res+=sum[i]+mark[i]*size[i]; } return res; } int main(void){ int x,y,id,z; scanf("%d%d",&n,&m); init(n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=sq;i++) for(int j=st[i];j<=ed[i];j++) sum[i]+=a[j]; for(int i=1;i<=m;i++){ scanf("%d",&id); if(id==1){ scanf("%d%d%d",&x,&y,&z); update(x,y,z); } else{ scanf("%d%d",&x,&y); printf("%lld\n",query(x,y)); } } return 0; }线段树算法：
#include<queue> #include<vector> #include<string> #include<math.h> #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; #define maxn 600005 #define ll long long ll sum[maxn],lazy[maxn]; int n,m; void build(int id,int l,int r){ if(l==r){ scanf("%lld",&sum[id]); return; } int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); sum[id]=sum[id*2]+sum[id*2+1]; } void pushDown(int id,int l,int r){ if(lazy[id]!=0){ int mid=(l+r)/2; sum[id*2]+=lazy[id]*(mid-l+1); sum[id*2+1]+=lazy[id]*(r-mid); lazy[id*2]+=lazy[id]; lazy[id*2+1]+=lazy[id]; lazy[id]=0; } } void update(int id,int l,int r,int ls,int rs,ll k){ if(l>r) return; if(ls<=l && rs>=r){ sum[id]+=k*(r-l+1); lazy[id]+=k; return; } pushDown(id,l,r); int mid=(l+r)/2; if(ls<=mid) update(id*2,l,mid,ls,rs,k); if(rs>mid) update(id*2+1,mid+1,r,ls,rs,k); sum[id]=sum[id*2]+sum[id*2+1]; } ll query(int id,int l,int r,int ls,int rs){ if(ls<=l && rs>=r) return sum[id]; ll res=0; int mid=(l+r)/2; pushDown(id,l,r); if(ls<=mid) res+=query(id*2,l,mid,ls,rs); if(rs>mid) res+=query(id*2+1,mid+1,r,ls,rs); return res; } int main(void){ int id,x,y; ll k; scanf("%d%d",&n,&m); build(1,1,n); for(int i=0;i<m;i++){ scanf("%d",&id); if(id==1){ scanf("%d%d%lld",&x,&y,&k); update(1,1,n,x,y,k); } else{ scanf("%d%d",&x,&y); printf("%lld\n",query(1,1,n,x,y)); } } return 0; }
