RT

#1 : AC

#2-10:WA

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

const int maxn = 1e5 + 10;

struct node
{
	int l, r;
	long long val;
	long long lazy;
};

node tree[maxn * 4];
long long a[maxn];
int n, m;

inline int lc(int x)
{
	return x << 1;
}

inline int rc(int x)
{
	return x << 1 | 1;
}

inline void build(int l, int r, int rt)
{
	if(l == r)
	{
		tree[rt].val = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, lc(rt));
	build(mid + 1, r, rc(rt));
	tree[rt].val = tree[lc(rt)].val + tree[rc(rt)].val;
	return;
}

inline void update(int l1, int r1, int v, int l, int r, int rt)
{
	if(l >= l1 && r <= r1)
	{
		tree[rt].val += v * (r - l + 1);
		tree[rt].lazy += v;
		return;
	}
	int mid = (l + r) >> 1;
	if(l1 <= mid)
		update(l1, r1, v, l, mid, lc(rt));
	if(r1 > mid)
		update(l1, r1, v, mid + 1, r, rc(rt));
	tree[rt].val = tree[lc(rt)].val + tree[rc(rt)].val;
	return;
}

inline void pushdown(int l, int r, int rt)
{
	if(tree[rt].lazy != 0)
	{
		tree[lc(rt)].lazy += tree[rt].lazy;
		tree[rc(rt)].lazy += tree[rt].lazy;
		tree[rt].lazy = 0;
		tree[lc(rt)].val += l * tree[lc(rt)].lazy;
		tree[rc(rt)].val += r * tree[rc(rt)].lazy;
	}
}

inline long long query(int l1, int r1, int l, int r, int rt)
{
	if(l >= l1 && r <= r1)
		return tree[rt].val;
	int mid = (l + r) >> 1;
	long long res = 0;
	pushdown(mid - l + 1, r - mid, rt);
	//pushdown(l, r, rt);
	if(l1 <= mid)
		res += query(l1, r1, l, mid, lc(rt));
	if(r1 > mid)
		res += query(l1, r1, mid + 1, r, rc(rt));
	return res;
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%lld", &a[i]);
	}
	build(1, n, 1);
	while(m --)
	{
		int x;
		scanf("%d", &x);
		if(x == 1)
		{
			int y, z, k;
			scanf("%d%d%d", &y, &z, &k);
			update(y, z, k, 1, n, 1);
		}
		else
		{
			int y, z;
			scanf("%d%d", &y, &z);
			printf("%lld\n", query(y, z, 1, n, 1));
		}
	}
	return 0;
}