0 PTS 求调

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

#define int long long
#define mid ((l + r) >> 1)
#define ls(x) (x << 1)
#define rs(x) ((x << 1) | 1)

const int N = 1e6 + 5;

int n, m;
int a[N], ans[N * 4], tag[N * 4];

void push_up(int p) { return ans[p] = ans[ls(p)] + ans[rs(p)], void(); }

void build(int p, int l, int r) {
	tag[p] = 0;
	if (l == r) return ans[p] = a[l], void();
	build(ls(p), l, mid);
	build(rs(p), mid + 1, r);
	push_up(p);
}

void push_down(int p, int l, int r) {
	tag[ls(p)] += tag[p], tag[rs(p)] += tag[p];
	ans[ls(p)] += tag[p] * (mid - l + 1);
	ans[rs(p)] += tag[p] * (r - mid);
	tag[p] = 0;
}

void insert(int nl, int nr, int l, int r, int p, int k) {
	if (nl <= l && r <= nr) 
		return ans[p] += k * (r - l + 1), tag[p] += k, void();
	push_down(p, l, r);
	if (nl <= mid) insert(nl, nr, l, mid, ls(p), k);
	if (nr > mid) insert(nl, nr, mid + 1, r, rs(p), k);
	push_up(p);
}

int query(int nl ,int nr, int l, int r, int p) {
	int cnt = 0;
	if (nl <= l && r <= nr) 
		return ans[p];
	push_down(p, l, r);
	if (nl <= mid) cnt += query(nl, nr, l, mid, ls(p));
	if (nr > mid) cnt += query(nl, nr, mid + 1, r, rs(p));
	return cnt;
}

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