lazy_propagation.cpp

#include <bits/stdc++.h>

using namespace std;

int const N = 1e5 + 1;
int n, m, a[N], type, s, e, v, seg[N * 4], lazy[N * 4];

void pro(int at, int l, int r) {
	seg[at] += lazy[at] * (r - l + 1);

	if(l != r)
		lazy[at << 1] += lazy[at],
		lazy[(at << 1) + 1] += lazy[at];

	lazy[at] = 0;
}

void build(int at, int l, int r) {
	if(l == r) {
		seg[at] = a[l];
		return;
	}

	int m = (l + r) / 2;
	build(at * 2, l, m);
	build(at * 2 + 1, m + 1, r);
	seg[at] = seg[at * 2] + seg[at * 2 + 1];
}

int get(int at, int l, int r) {
	if(lazy[at] != 0)
		pro(at, l, r);

	if(l > e || r < s)
		return 0;

	if(l >= s && r <= e)
		return seg[at];

	int m = (l + r) / 2;
	return get(at * 2, l, m) + get(at * 2 + 1, m + 1, r);
}

void update(int at, int l, int r) {
	if(lazy[at] != 0)
		pro(at, l, r);

	if(l > e || r < s)
		return;

	if(l >= s && r <= e) {
		lazy[at] += v;
		pro(at, l, r);
		return;
	}

	int m = (l + r) / 2;
	update(at * 2, l, m);
	update(at * 2 + 1, m + 1, r);
	seg[at] = seg[at * 2] + seg[at * 2 + 1];
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
#endif

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
	}

	build(1, 1, n);

	scanf("%d", &m);

	for (int i = 0; i < m; ++i) {
		scanf("%d", &type);

		if(type == 1) {
			scanf("%d %d", &s, &e);
			printf("%d\n", get(1, 1, n));
		} else {
			scanf("%d %d %d", &s, &e, &v);
			update(1, 1, n);
		}
	}

	return 0;
}