题目链接：
题目描述
如题，已知一个数列，你需要进行下面两种操作：
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
解题思路：
线段树区间修改，区间查询，lazy标记，模板。
每更新一次本层的lazy标记，将lazy标记下方一层。
1 #include2 #include 3 #define ll long long 4 /* run this program using the console pauser or add your own getch, system("pause") or input loop */ 5 using namespace std; 6 //ll tree[100010*4]; 7 ll sum[100010*4];//维护一个区间的总和 8 ll lazy[100010*4];//lazy标记下放 9 ll a[100010];10 void build(ll p,ll l,ll r){11 if(l==r){12 sum[p]=a[l];return;13 }14 ll mid=(l+r)>>1;15 build(p<<1,l,mid);16 build(p<<1|1,mid+1,r);17 sum[p]=sum[p<<1]+sum[p<<1|1];18 }19 void pushDown(ll p,ll m){ //m为区间长度 20 //下放标记，清空lazy的值21 if(lazy[p]){22 lazy[p<<1]+=lazy[p];23 lazy[p<<1|1]+=lazy[p]; 24 sum[p<<1]+=(m-(m>>1))*lazy[p];//左子树,位于运算加括号 25 sum[p<<1|1]+=(m>>1)*lazy[p];//右子树 26 // sum[p<<1]+=(m>>1)*lazy[p];27 // sum[p<<1|1]+=(m-m>>1)*lazy[p];//右边是一半 28 29 lazy[p]=0;30 }31 } 32 void change(ll p,ll l,ll r,ll a,ll b,ll c){33 if(a<=l&&r<=b){34 lazy[p]+=c;35 sum[p]+=c*(r-l+1);36 return;37 } 38 pushDown(p,r-l+1);39 ll mid=(l+r)>>1;40 if(a<=mid) change(p<<1,l,mid,a,b,c);41 if(b>mid) change(p<<1|1,mid+1,r,a,b,c);42 43 sum[p]=sum[p<<1]+sum[p<<1|1];//p<<1|1=p*2+1;44 }45 ll Find(ll p,ll l,ll r,ll x,ll y){46 if(x<=l&&r<=y){47 return sum[p];48 }49 ll mid=(l+r)>>1;50 pushDown(p,r-l+1);51 ll ret=0;52 if(x<=mid) ret+=Find(p<<1,l,mid,x,y);53 if(y>mid) ret+=Find(p<<1|1,mid+1,r,x,y);54 // if(y>mid) return ret+=Find(p<<1|1,mid+1,r,x,y);55 // if(x<=mid) return ret+=Find(p<<1,l,mid,x,y);56 // if(x<=mid) return ret+Find(p<<1,l,mid,x,y);//加上两部分的值 57 // if(y>mid) return ret+Find(p<<1|1,mid+1,r,x,y);58 59 return ret;60 }61 int main(int argc, char** argv) {62 // freopen("C:/Users/Xzq/Desktop/p1.txt","r",stdin);63 ll n,m;64 scanf("%lld %lld",&n,&m);65 for(ll i=1;i<=n;i++) scanf("%d",&a[i]); 66 build(1,1,n);67 // for(ll i=1;i<=8;i++) printf("sum[%d]=%d\n",i,sum[i]);68 69 while(m--){70 ll op;scanf("%lld",&op);71 if(op==1){72 ll x,y,k;scanf("%lld %lld %lld",&x,&y,&k);73 change(1,1,n,x,y,k);74 }75 else if(op==2){76 ll x,y;scanf("%lld %lld",&x,&y);77 ll ans=Find(1,1,n,x,y);78 printf("%lld\n",ans);79 }80 }81 return 0;82 }