rt，20pts

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
mt19937 rng(time(0));
int root,tot;
struct node
{
	int sum,val,pri,ls,rs,sz;
	int add;
}tr[N];
void pushup(int p)
{
	tr[p].sum=tr[p].val+tr[tr[p].ls].sum+tr[tr[p].rs].sum;
	tr[p].sz=tr[tr[p].ls].sz+tr[tr[p].rs].sz+1;
}
int New(int x)
{
	++tot;
	tr[tot].val=x;
	tr[tot].pri=rng();
	tr[tot].sz=1;
	return tot;
}
void addtag(int p,int d)
{
	tr[p].val+=d;
	tr[p].sum+=tr[p].sz*d;
	tr[p].add+=d;
}
void pushdown(int p)
{
	if(tr[p].add)
	{
		if(tr[p].ls)
			addtag(tr[p].ls,tr[p].add);
		if(tr[p].rs)
			addtag(tr[p].rs,tr[p].add);
		tr[p].add=0;
	}
}
void split(int p,int k,int &L,int &R)
{
	if(!p)
	{
		L=R=0;
		return ;
	}
	pushdown(p);
	if(tr[tr[p].ls].sz<k)
	{
		L=p;
		split(tr[p].rs,k-tr[tr[p].ls].sz-1,tr[p].rs,R);
	}
	else
	{
		R=p;
		split(tr[p].ls,k,L,tr[p].ls);
	}
	pushup(p);
}
int merge(int L,int R)
{
	if(!L||!R)
		return L|R;
	if(tr[L].pri<=tr[R].pri)
	{
		pushdown(L);
		tr[L].rs=merge(tr[L].rs,R);
		pushup(L);
		return L;
	}
	pushdown(R);
	tr[R].ls=merge(L,tr[R].ls);
	pushup(R);
	return R;
}
void update(int l,int r,int d)
{
	int L,R,p;
	split(root,l-1,L,R);
	split(R,r-l+1,R,p);
	addtag(R,d);
	root=merge(L,merge(R,p));
}
int query(int l,int r)
{
	int L,R,p;
	split(root,l-1,L,R);
	split(R,r-l+1,R,p);
	int res=tr[R].sum;
	root=merge(L,merge(R,p));
	return res;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		int x;
		cin>>x;
		root=merge(root,New(x));
	}
	while(m--)
	{
		int op,x,y,k;
		cin>>op>>x>>y;
		if(op==1)
			cin>>k,update(x,y,k);
		else
			cout<<query(x,y)<<'\n';
	}
}