seg_lazy.cpp

// Segment Tree with Lazy Propagation
// Thiago Mota

#include <bits/stdc++.h>
#define L (seg<<1)
#define R (L|1)
#define meio ((ini+fim)>>1)

using namespace std;
const int maxn = 1e3 + 10;
int tree[4*maxn], lazy[4*maxn], v[maxn];
int n;

void build(int seg=1, int ini=1, int fim=n){
	if(ini == fim){
		tree[seg] = v[ini];
		return;
	}

	build(L, ini, meio);
	build(R, meio+1, fim);
	tree[seg] = tree[L] + tree[R];
}

void flush(int seg, int ini, int fim){
	if(lazy[seg] == 0) return;

	if(L < 4*maxn) lazy[L] += lazy[seg];
	if(R < 4*maxn) lazy[R] += lazy[seg];

	tree[seg] = (fim-ini+1)*lazy[seg];
	lazy[seg] = 0;
}

void update(int l, int r, int v, int seg=1, int ini=1, int fim=n){
	if(ini > r || fim < l) return;
	flush(seg, ini, fim);	

	if(l <= ini && fim <= r){
		lazy[seg] += v;
		flush(seg, ini, fim);
		return;
	}

	update(l, r, v, L, ini, meio);
	update(l, r, v, R, meio+1, fim);
	tree[seg] = tree[L] + tree[R];
}

int query(int l, int r, int seg=1, int ini=1, int fim=n){
	if(ini > r || fim < l) return 0;
	flush(seg, ini, fim);

	if(l <= ini && fim <= r) return tree[seg];

	int p1 = query(l, r, L, ini, meio);
	int p2 = query(l, r, R, meio+1, fim);
	return p1+p2;
}

int main(){
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> v[i];

	build();
	int q;
	while(cin >> q && q){
		if(q == 1){
			int l, r, v;
			cin >> l >> r >> v;
			update(l, r, v);
		}else{
			int l, r;
			cin >> l >> r;
			cout << query(l, r) << "\n";
		}
	}
	return 0;
}