RT
蒟蒻尝试用 FHQ-Treap 写此题，
然后自闭了。。。
样例没过。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m;
int opt, l, r;
long long x;
struct FHQ_Treap{
	int root, total;
	int u, v, w;
	int result;
	struct Node{
		int position;
		long long value;
		int priority;
		long long sum;
		long long add;
		int left;
		int right;
	};
	Node tree[MAXN];
	void Initialize()
	{
		srand(time(NULL));
		root = total = 0;
		tree[0].position = 0;
		tree[0].value = 0;
		tree[0].priority = 0;
		tree[0].sum = 0;
		tree[0].add = 0;
		tree[0].left = 0;
		tree[0].right = 0;
		return;
	}
	int Make_Node(int position, long long value)
	{
		total++;
		tree[total].position = position;
		tree[total].value = value;
		tree[total].priority = rand();
		tree[total].sum = value;
		tree[total].add = 0;
		tree[total].left = 0;
		tree[total].right = 0;
		return total;
	}
	void Push_Up(int u)
	{
		tree[u].sum = tree[tree[u].left].sum + tree[tree[u].right].sum + tree[u].value;
		return;
	}
	void Push_Down(int u, int l, int r)
	{
		if(tree[u].add == 0) return;
		tree[tree[u].left].value += tree[u].add;
		tree[tree[u].right].value += tree[u].add;
		tree[tree[u].left].sum += tree[u].sum * (r - l + 1);
		tree[tree[u].right].sum += tree[u].sum * (r - l + 1);
		tree[tree[u].left].add += tree[u].add;
		tree[tree[u].right].add += tree[u].add;
		tree[u].add = 0;
		return;
	}
	void Split(int position, int w, int &u, int &v)
	{
		if(w == 0){
			u = v = 0;
			return;
		}
		if(tree[w].position <= position){
			u = w;
			Split(position, tree[w].right, tree[w].right, v);
		}
		if(tree[w].position > position){
			v = w;
			Split(position, tree[w].left, u, tree[w].left);
		}
		Push_Down(w);
		Push_Up(w);
		return;
	}
	int Merge(int u, int v)
	{
		if(u == 0 || v == 0) return u + v;
		if(tree[u].priority <= tree[v].priority){
			tree[u].right = Merge(tree[u].right, v);
			Push_Down(u);
			Push_Up(u);
			return u;
		}
		if(tree[u].priority > tree[v].priority){
			tree[v].left = Merge(u, tree[v].left);
			Push_Down(v);
			Push_Up(v);
			return v;
		}
	}
	void Insert(int position, long long value)
	{
		Split(position-1, root, u, v);
		root = Merge(Merge(u, Make_Node(position, value)), v);
		return;
	}
	void Add(int l, int r, long long value)
	{
		Split(l-1, root, u, v);
		Split(r, v, v, w);
		tree[v].value += value;
		tree[v].add += value;
		Push_Down(v);
		Push_Up(v);
		root = Merge(Merge(u, v), w);
		return;
	}
	long long Query(int l, int r)
	{
		Split(l-1, root, u, v);
		Split(r, v, v, w);
		result = tree[v].sum;
		root = Merge(Merge(u, v), w);
		return result;
	}
};
FHQ_Treap t;
int main()
{
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++){
		scanf("%d", &x);
		t.Insert(i, x);
	}
	while(m--){
		scanf("%d%d%d", &opt, &l, &r);
		if(opt == 1){
			scanf("%d", &x);
			t.Add(l, r, x);
		}
		if(opt == 2) printf("%d\n", t.Query(l, r));
	}
	return 0;
}
//FHQ-Treap
//样例未过