题目描述
如题，已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 kk。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数 n, mn,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 nn 个用空格分隔的整数，其中第 ii 个数字表示数列第 ii 项的初始值。
接下来 mm 行每行包含 33 或 44 个整数，表示一个操作，具体如下：
1 x y k：将区间 [x, y][x,y] 内每个数加上 kk。2 x y：输出区间 [x, y][x,y] 内每个数的和。
输出格式
输出包含若干行整数，即为所有操作 2 的结果。
输入输出样例
输入
5 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4
输出
11 8 20
献上板子：
/*Keep on going Never give up*/
#include <bits/stdc++.h>
using namespace std;
#define MAX 0x7fffffff
#define int long long
const int mod = 1e9+7;
const int maxn = 1e6+1000;
#define pi acos(-1.0)
int n,m,a[maxn];
struct tree{int l,r,val,add;
}t[4*maxn+2];
void bulid(int p,int l,int r){t[p].l=l;t[p].r=r;//以p为编号的节点维护的区间为l到rif(l==r){//l=r的话，这个区间就只有一个数，直接让区间维护的值等于a[i]t[p].val=a[l];return;}//否则维护的值等于左儿子加右儿子int mid=l+r>>1;bulid(p*2,l,mid);bulid(p*2+1,mid+1,r);t[p].val=t[p*2].val+t[p*2+1].val;
}
void spread(int p){if(t[p].add){//如果懒标记不为0，就将其下传，修改左右儿子维护的值t[p*2].val+=t[p].add*(t[p*2].r-t[p*2].l+1);t[p*2+1].val+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);t[p*2].add+=t[p].add;//为该节点的左右儿子打上标记t[p*2+1].add+=t[p].add;t[p].add=0;//下传之后将该节点的懒标记清0}
}
void change(int p,int x,int y,int z){if(x<=t[p].l && y>=t[p].r){//被覆盖的话，就对其进行修改t[p].val+=z*(t[p].r-t[p].l+1);t[p].add+=z;//打上懒标记return;}spread(p);//如果发现没有被覆盖，那就需要继续向下找，考虑儿子所维护的区间可能因为懒标记的存在而没有修改，因此将懒标记下放int mid=t[p].l+t[p].r>>1;if(x<=mid) change(p*2,x,y,z);//如果要修改的区间覆盖了左儿子，就修改左儿子if(y>mid) change(p*2+1,x,y,z);//右儿子同理t[p].val=t[p*2].val+t[p*2+1].val;//最终维护的值等于左儿子的值+右儿子的值
}
int ask(int p,int x,int y){if(x<=t[p].l && y>=t[p].r) return t[p].val;//如果被覆盖，就返回维护的值spread(p);//下传懒标记，并查询左右儿子int mid=t[p].l+t[p].r>>1;int ans=0;if(x<=mid) ans+=ask(p*2,x,y);if(y>mid) ans+=ask(p*2+1,x,y);//累加答案，返回左右儿子的和return ans;
}
signed main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);bulid(1,1,n);for(int i=1;i<=m;i++){int q,x,y,z;scanf("%lld",&q);if(q==1){scanf("%lld%lld%lld",&x,&y,&z);change(1,x,y,z);}else{scanf("%lld%lld",&x,&y);printf("%lld\n",ask(1,x,y));}}
}