P3372，10pts，优化中，求调

#include <bits/stdc++.h>
using namespace std;

struct tree
{
	long long l,r;
	long long value;//一段区间的和 
	long long lazynote;
}t[4000005];

long long n,m;
long long a[1000005];

long long left(long long k)
{
	return k<<1;
}

long long right(long long k)
{
	return (k<<1)|1;
}

void build(long long l,long long r,long long node)//建树
{
	t[node].l=l;
	t[node].r=r;
	if(l==r)
	{
		t[node].value=a[l];
	}
	else
	{
		long long mid=(l+r)>>1;
		build(l,mid,left(node));
		build(mid+1,r,right(node));
		t[node].value=t[left(node)].value+t[right(node)].value;
	}
	return;
}

void removelazynote(long long k)//移除懒标记
{
	if(t[k].lazynote)
	{
		t[left(k)].value+=t[k].lazynote*(t[left(k)].r-t[left(k)].l+1);
		t[left(k)].lazynote+=t[k].lazynote;
		t[right(k)].value+=t[k].lazynote*(t[right(k)].r-t[right(k)].l+1);
		t[right(k)].lazynote+=t[k].lazynote;
		t[k].lazynote=0;
	}
}

void change(long long p,long long x,long long y,long long k)
{
	if(x<=t[p].l&&t[p].r<=y)//只用这个节点
	{
		t[p].value+=k*(t[p].r-t[p].l+1);
		t[p].lazynote=k;
		return;
	}
	removelazynote(p);//要用到子节点
	long long mid=(t[p].l+t[p].r)>>1;
	if(x<=mid)change(left(p),x,min(y,mid),k);
	if(mid<y)change(right(p),max(x,mid+1),y,k);
	t[p].value=t[left(p)].value+t[right(p)].value;
}

long long query(long long p,long long x,long long y)
{
	if(x==t[p].l&&y==t[p].r)//只用这个节点
	{
		return t[p].value;
	}
	removelazynote(p);//要用到子节点
	long long mid=(t[p].l+t[p].r)>>1;
	long long ans=0;
	if(x<=mid)
	{
		ans+=query(left(p),x,min(y,mid));	
	}
	if(mid<y)
	{
		ans+=query(right(p),max(x,mid+1),y);
	}
	return ans;
}

int main()
{
	cin>>n>>m;
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	build(1,n,1);
	long long n1,x,y,k;
	for(long long i=1;i<=m;i++)
	{
		scanf("%lld %lld %lld",&n1,&x,&y);
		if(n1==1)
		{
			scanf("%lld",&k);
			change(1,x,y,k);
		}
		else if(n1==2)
		{
			cout<<query(1,x,y)<<"\n";
		}
	}
	return 0;
}