aya，用的分块

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e6+10;
int tag[N],tl[N],tr[N],a[N],B;
int q[N],C[N];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void build()
{
	int B=sqrt(n);
	for(int k=1;k<=(n-1)/B+1;k++)
	{
		for(int i=(k-1)*B+1;i<=min(k*B,n);i++)
		{
			tag[i]=k;
			tl[i]=(k-1)*B+1;
			tr[i]=min(k*B,n);
		}
	}
	return ;
}
inline void add_on(int x,int y,int k){
	int B=sqrt(n);
	if(tag[x]==tag[y]){
		for(int i=x;i<=y;i++)
		{
			a[i]+=k;
		}
		return ;
	}
	else{
		for(int i=tag[x]+1;i<=tag[y]-1;i++)
		{
			C[i]+=k;
		}
		for(int i=x;i<=tr[x];i++ )
		{
			a[i]+=k;
		}
		for(int i=tl[y];i<=y;i++)
		{
			a[i]+=k;
		}
		return ;
	} 
	return ;
}
inline void ques(int x,int y)
{
	int B=sqrt(n);
	int ans=0;
	if(tag[x]==tag[y])
	{
		for(int i=x;i<=y;i++)
		{
			ans+=a[i]+C[tag[i]]-q[tag[i]];
		}
		cout<<ans<<endl;
		return ;
	}
	else{
//		for(int i=x;i<=y;i++)
//		{
//			ans+=a[i]+C[tag[i]];
//		}
		for(int i=x;i<=tr[x];i++)
		{
			ans+=a[i]+C[tag[x]]-q[tag[x]];
		}
		for(int i=tl[y];i<=y;i++)
		{
			ans+=a[i]+C[tag[y]]-q[tag[y]];
		}
		for(int i=tag[x]+1;i<=tag[y]-1;i++)
		{
			ans+=C[i];
		}
		cout<<ans<<endl;
	}
	return ;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=sqrt(n);i++)
	{
		for(int j=(i-1)*sqrt(n)+1;j<=min(i*(int)sqrt(n),n);j++)
			C[i]+=a[j],q[i]=C[i];
	}
	build();
	for(int i=1;i<=m;i++){
		int k=read();
		if(k==1)
		{
			int x=read(),y=read(),t=read();
			add_on(x,y,t);
		}
		else 
		{
			int x=read(),y=read();
			ques(x,y);
		}
	}
	return 0;
}