【问题描述】
给定一个长为n的序列，有m次操作，每次操作对序列某段区间内所有数加上一个数或者询问一段区间的和。
【程序】
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,m,a[500001],add[500001]; 5 long long sum[500001]; 6 7 void build(int k,int l,int r) //建树 8 { 9 if (l==r) //当前为叶节点 10 { 11 sum[k]=a[l]; 12 return ; 13 } 14 int mid=(l+r)>>1; 15 build(k*2,l,mid); //左子树 16 build(k*2+1,mid+1,r); //右子树 17 sum[k]=sum[k*2]+sum[k*2+1]; 18 } 19 20 void Add(int k,int l,int r,int v) //区间加值并更新 21 { 22 add[k]+=v; //打标记 23 sum[k]+=(long long)v*(r-l+1); //维护区间和 24 } 25 26 void pushdown(int k,int l,int r,int mid) //标记下放 27 { 28 if (add[k]==0) //没有标记 29 return ; 30 else 31 { 32 Add(k*2,l,mid,add[k]); //下传到左子树 33 Add(k*2+1,mid+1,r,add[k]); //下传到右子树 34 add[k]=0; //清零标记 35 } 36 } 37 38 long long query(int k,int l,int r,int x,int y) //询问 39 { 40 if (x<=l&&r<=y) 41 return sum[k]; 42 int mid=(l+r)>>1; 43 long long ans=0; 44 pushdown(k,l,r,mid); //下传标记 45 if (x<=mid) 46 ans+=query(k*2,l,mid,x,y); 47 if (mid<y) 48 ans+=query(k*2+1,mid+1,r,x,y); 49 return ans; 50 } 51 52 void modify(int k,int l,int r,int x,int y,int v) //区间和 53 { 54 if (x<=l&&r<=y) 55 return Add(k,l,r,v); 56 int mid=(l+r)>>1; 57 pushdown(k,l,r,mid); //到达每一个结点都要下传标记 58 if (x<=mid) 59 modify(k*2,l,mid,x,y,v); 60 if (mid<y) 61 modify(k*2+1,mid+1,r,x,y,v); 62 sum[k]=sum[k*2]+sum[k*2+1]; //更新下传之后的最新值 63 } 64 65 int main() 66 { 67 scanf("%d%d",&n,&m); 68 for (int i=1;i<=n;i++) 69 scanf("%d",&a[i]); 70 build(1,1,n); //建树 71 while (m--) 72 { 73 int op,x,y,v; 74 scanf("%d",&op); 75 if (op==1) //在x到y的区间内每个数加上v 76 { 77 scanf("%d%d%d",&x,&y,&v); 78 modify(1,1,n,x,y,v); 79 } 80 if (op==2) //查询x到y的区间和 81 { 82 scanf("%d%d",&x,&y); 83 printf("%lld\n",query(1,1,n,x,y)); 84 } 85 } 86 return 0; 87 }
再附一份没有注释的代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,m,a[500001],add[500001]; 5 long long sum[500001]; 6 7 void build(int k,int l,int r) 8 { 9 if (l==r) 10 { 11 sum[k]=a[l]; 12 return ; 13 } 14 int mid=(l+r)>>1; 15 build(k*2,l,mid); 16 build(k*2+1,mid+1,r); 17 sum[k]=sum[k*2]+sum[k*2+1]; 18 } 19 20 void Add(int k,int l,int r,int v) 21 { 22 add[k]+=v; 23 sum[k]+=(long long)v*(r-l+1); 24 } 25 26 void pushdown(int k,int l,int r,int mid) 27 { 28 if (add[k]==0) 29 return ; 30 else 31 { 32 Add(k*2,l,mid,add[k]); 33 Add(k*2+1,mid+1,r,add[k]); 34 add[k]=0; 35 } 36 } 37 38 long long query(int k,int l,int r,int x,int y) 39 { 40 if (x<=l&&r<=y) 41 return sum[k]; 42 int mid=(l+r)>>1; 43 long long ans=0; 44 pushdown(k,l,r,mid); 45 if (x<=mid) 46 ans+=query(k*2,l,mid,x,y); 47 if (mid<y) 48 ans+=query(k*2+1,mid+1,r,x,y); 49 return ans; 50 } 51 52 void modify(int k,int l,int r,int x,int y,int v) 53 { 54 if (x<=l&&r<=y) 55 return Add(k,l,r,v); 56 int mid=(l+r)>>1; 57 pushdown(k,l,r,mid); 58 if (x<=mid) 59 modify(k*2,l,mid,x,y,v); 60 if (mid<y) 61 modify(k*2+1,mid+1,r,x,y,v); 62 sum[k]=sum[k*2]+sum[k*2+1]; 63 } 64 65 int main() 66 { 67 scanf("%d%d",&n,&m); 68 for (int i=1;i<=n;i++) 69 scanf("%d",&a[i]); 70 build(1,1,n); 71 while (m--) 72 { 73 int op,x,y,v; 74 scanf("%d",&op); 75 if (op==1) 76 { 77 scanf("%d%d%d",&x,&y,&v); 78 modify(1,1,n,x,y,v); 79 } 80 if (op==2) 81 { 82 scanf("%d%d",&x,&y); 83 printf("%lld\n",query(1,1,n,x,y)); 84 } 85 } 86 return 0; 87 }