Luogu P3371 线段树1

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson  l,mid,rt<<1
#define rson  mid+1,r,rt<<1|1
using namespace std;
const int N = 100010;
typedef long long LL;
LL sum[N << 2],add[N << 2],a[N],n,m;
void update(int rt)
{
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void build(int l,int r,int rt)
{
	add[rt] = 0;
	if(l == r)
	{
		scanf("%lld",&sum[rt]);
		return;
	}
	int mid = (l+r)>>1;
	build(lson);
	build(rson);
	update(rt);
}
void pushdown(int rt,int len)
{
	if(add[rt] == 0) return;
	add[rt<<1] += add[rt]; 
	add[rt<<1|1] += add[rt];
	sum[rt<<1] += add[rt]*(len - (len>>1));
	sum[rt<<1|1] += add[rt]*(len>>1);
	add[rt] = 0;
}
void modify(int l,int r,int rt,int ql,int qr,int v)
{
	if(ql <= l && r <= qr)
	{
		add[rt] += v;
		sum[rt] += (LL)v*(r-l+1);
		return;
	}
	int mid = (l+r)>>1;
	pushdown(rt,r-l+1);
	if(ql <= mid) modify(lson,ql,qr,v);
	if(mid < qr) modify(rson,ql,qr,v);
	update(rt);
}
LL query(int l,int r,int rt,int ql,int qr)
{
	if(ql <= l && r <= qr) return sum[rt];
	int mid = (l+r)>>1;
	pushdown(rt,r-l+1);
	ll res = 0;
	if(ql <= mid) res += query(lson,ql,qr);
	if(mid < qr) res += query(rson,ql,qr);
	return res;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	build(1,n,1);
	for(int i = 1;i <= m;++i)
	{
		LL qt;
		scanf("%lld",&qt);
		if(qt == 1)
		{
			LL x,y,k;
			scanf("%lld%lld%lld",&x,&y,&k);
			modify(1,n,1,x,y,k);
		}else{
			LL x,y;
			scanf("%lld%lld",&x,&y);
			printf("%lld
",query(1,n,1,x,y));
		}
	}
	
	return 0;
}