题目描述
如题，已知一个数列，你需要进行下面两种操作：
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的结果。
输入输出样例
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
样例说明：
1 #include<iostream> 2 #include<cstdio> 3 #define ll long long 4 using namespace std; 5 ll read() 6 { 7 ll x=0,f=1; 8 char ch=getchar(); 9 while(ch<'0'||ch>'9') 10 { 11 if(ch=='-') 12 f=-1; 13 ch=getchar(); 14 } 15 while(ch>='0'&&ch<='9') 16 { 17 x=x*10+ch-'0'; 18 ch=getchar(); 19 } 20 return x*f; 21 } 22 ll n,m,a,b,t,x,y,z; 23 ll tree[100005],tree1[100005]; 24 void add(ll*z,ll x,ll num) 25 { 26 while(x<=n) 27 { 28 z[x]+=num; 29 x+=x&(-x); 30 } 31 } 32 ll getsum(ll*z,ll x) 33 { 34 ll sum=0; 35 while(x>0) 36 { 37 sum+=z[x]; 38 x-=x&(-x); 39 } 40 return sum; 41 } 42 int main() 43 { 44 n=read(),m=read(); 45 for(ll i=1; i<=n; i++) 46 { 47 a=read(); 48 b=a-b; 49 add(tree,i,b); 50 add(tree1,i,(i-1)*b); 51 b=a; 52 } 53 for(ll i=1; i<=m; i++) 54 { 55 t=read(); 56 if (t==1) 57 { 58 x=read(),y=read(),z=read(); 59 add(tree,x,z); 60 add(tree,y+1,-z); 61 add(tree1,x,z*(x-1)); 62 add(tree1,y+1,-z*y); 63 } 64 else 65 { 66 x=read(),y=read(); 67 printf("%lld ",(y*getsum(tree,y)-(x-1)*getsum(tree,x-1))-(getsum(tree1,y)-getsum(tree1,x-1))); 68 } 69 } 70 return 0; 71 }