机房大佬亲授线段树

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
int n,m;
struct node
{
	int ord,add,imp,left,right;
}tree[4000005];
inline int build(int k,int x,int y)
{
	tree[k].left=x;
	tree[k].right=y;
	if(x==y)
	{
		tree[k].imp=tree[x].ord;
		return 0;
	}
	int mid=(x+y)>>1;
	build(k<<1,x,mid);
	build(k<<1|1,mid+1,y);
	tree[k].imp=tree[k<<1].imp+tree[k<<1|1].imp;
}
inline void down(int k)
{
	if(tree[k].add==0) return ;
	tree[k<<1].add+=tree[k].add;
	tree[k<<1|1].add+=tree[k].add;
	tree[k<<1].imp+=(tree[k<<1].right-tree[k<<1].left+1)*tree[k].add;
	tree[k<<1|1].imp+=(tree[k<<1|1].right-tree[k<<1|1].left+1)*tree[k].add;
	tree[k].add=0;
}
inline void update(int k,int x,int y,int a)
{
	if(x<=tree[k].left&&y>=tree[k].right)
	{
		tree[k].add+=a;
		tree[k].imp+=(tree[k].right-tree[k].left+1)*tree[k].add;
		return ;
	}
	down(k<<1);
	down(k<<1|1);
	if(x<=tree[k<<1].right) update(k<<1,x,y,a);
	if(y>=tree[k<<1|1].left) update(k<<1|1,x,y,a);
	tree[k].imp=tree[k<<1].imp+tree[k<<1|1].imp;
}
inline int check(int k,int x,int y)
{
	if(x<=tree[k].left&&y>=tree[k].right) return tree[k].imp;
	down(k<<1);
	down(k<<1|1);
	int ans=0;
	if(x<=tree[k<<1].right) ans+=check(k<<1,x,y);
	if(y>=tree[k<<1|1].left) ans+=check(k<<1|1,x,y);
	return ans;
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&tree[i].ord);
	}
	build(1,1,n);
	while (m--)
	{
		int t,x,y,k;
		scanf("%lld",&t);
		if(t==1)
		{
			scanf("%lld%lld%lld",&x,&y,&k);
			update(1,x,y,k);
		}
		else
		{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",check(1,x,y));
		}
	}
	return 0;
}