P3372 【模板】线段树 1
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式：输出包含若干行整数，即为所有操作2的结果。
输入输出样例
输入样例#1：
5 51 5 4 2 32 2 41 2 3 22 3 41 1 5 12 1 4
输出样例#1：
11820
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
样例说明：
既然是模板，就不做解释了。
代码如下：
1 // LUOGU 3372 【模板】线段树1 2 // 2017.7.20 19:34 3 #include4 #define MAXN 100000 5 #define MAXT MAXN*4 6 using namespace std; 7 int N,M,topt=0; 8 long long a[MAXN+2]; 9 struct sgt_node{10 int lc,rc;11 long long sum,lazy;12 }sgt[MAXT+2];13 #define lch sgt[now].lc14 #define rch sgt[now].rc15 #define smid ((l+r)>>1)16 void update(int now){17 sgt[now].sum=sgt[lch].sum+sgt[rch].sum;18 }19 void set_lazy(int now,int l,int r,long long v){20 sgt[now].sum+=(r-l+1)*v;21 sgt[now].lazy+=v;22 }23 void push_down(int now,int l,int r){24 if(sgt[now].lazy){25 set_lazy(lch,l,smid,sgt[now].lazy);26 set_lazy(rch,smid+1,r,sgt[now].lazy);27 sgt[now].lazy=0;28 }29 }30 void Build_sgt(int &now,int l,int r){31 now=++topt;32 if(l==r){33 sgt[now].sum=a[l];34 return;35 }36 Build_sgt(lch,l,smid);37 Build_sgt(rch,smid+1,r);38 update(now);39 }40 long long Query_sgt(int now,int l,int r,int qx,int qy){41 if(l==qx&&r==qy)return sgt[now].sum;42 push_down(now,l,r);43 if(qy<=smid)return Query_sgt(lch,l,smid,qx,qy);44 if(qx>smid)return Query_sgt(rch,smid+1,r,qx,qy);45 return Query_sgt(lch,l,smid,qx,smid)+Query_sgt(rch,smid+1,r,smid+1,qy);46 }47 void Region_add(int now,int l,int r,int x,int y,long long v){48 if(l==x&&r==y){49 set_lazy(now,l,r,v);50 return;51 }52 push_down(now,l,r);53 if(y<=smid)Region_add(lch,l,smid,x,y,v);54 else if(x>smid)Region_add(rch,smid+1,r,x,y,v);55 else{56 Region_add(lch,l,smid,x,smid,v);57 Region_add(rch,smid+1,r,smid+1,y,v);58 }59 update(now);60 }61 int main(){62 scanf("%d%d",&N,&M);63 for(int i=1;i<=N;i++)64 scanf("%lld",a+i);65 int root=0;66 Build_sgt(root,1,N);67 int op,x,y;68 long long k;69 for(int i=1;i<=M;i++){70 scanf("%d",&op);71 switch(op){72 case 1:73 scanf("%d%d%lld",&x,&y,&k);74 Region_add(1,1,N,x,y,k);75 break;76 case 2:77 scanf("%d%d",&x,&y);78 printf("%lld\n",Query_sgt(1,1,N,x,y));79 break;80 }81 }82 return 0;83 }