题目描述
如题，已知一个数列，你需要进行下面两种操作：
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 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4
输出 #1
11 8 20
说明/提示
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
样例说明：
题解：第一遍：woc我线段树一遍过！（样例对了）还跟旁边的小哥哥得瑟
提交……emmmm 10分？？？？？
第二遍：哈哈哈哈原来add没清零，自信提交：emmm70？？？
第三遍：原来要开long long啊……A了
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<bits/stdc++.h> using namespace std; const int N=100002; typedef long long ll; ll z,k,sum[N*4],add[N*4],a[N]; int n,ques,pd,x,y; void pushup(int rt) { sum[rt]=sum[rt*2]+sum[rt*2+1]; } void pushdown(int rt,int ln,int rn){ if(add[rt]){ add[rt*2]+=add[rt]; add[rt*2+1]+=add[rt]; sum[rt*2]+=add[rt]*ln; sum[rt*2+1]+=add[rt]*rn; add[rt]=0; } } void build(int l,int r,int rt){ if(l==r){ sum[rt]=a[l]; return ; } int m=(l+r)/2; build(l,m,rt*2); build(m+1,r,rt*2+1); pushup(rt); } void update(int L,int R,ll val,int l,int r,int rt){ if(L<=l && R>=r){ sum[rt]+=val*(r-l+1); add[rt]+=val; return ; } int m=(l+r)/2; pushdown(rt,m-l+1,r-m); if(L<=m) update(L,R,val,l,m,rt*2); if(R>m) update(L,R,val,m+1,r,rt*2+1); pushup(rt); } ll query(int L,int R,int l,int r,int rt){ if(L<=l && R>=r) return sum[rt]; int m=(l+r)/2; ll ans=0; pushdown(rt,m-l+1,r-m); if(L<=m) ans+=query(L,R,l,m,rt*2); if(R>m) ans+=query(L,R,m+1,r,rt*2+1); return ans; } int main(){ freopen("3372.in","r",stdin); freopen("3372.out","w",stdout); scanf("%d %d",&n,&ques); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,n,1); while(ques--){ scanf("%d",&pd); if(pd==1){ scanf("%d %d %d",&x,&y,&z); update(x,y,z,1,n,1); } else{ scanf("%d %d",&x,&y); printf("%lld ",query(x,y,1,n,1)); } } return 0; }