代码

#include <iostream>
#define ll long long 

using namespace std;

const int N = 123456;
ll sum[N<<2], tag[N<<2], a[N], n;
inline void update(int p) { sum[p] = sum[p<<1] + sum[p<<1|1]; }
inline void spread(int p, int llen, int rlen) {
	tag[p<<1] += tag[p];
	tag[p<<1|1] += tag[p];
	sum[p<<1] += tag[p] * llen;
	sum[p<<1|1] += tag[p] * rlen;
	tag[p] = 0;
}
void build(int p, int lp, int rp) {
	if(lp == rp) {
		sum[p] = a[lp];
		tag[p] = 0;
		return;
	}
	int mid = (lp + rp) >> 1;
	build(p<<1, lp, mid);
	build(p<<1|1, mid + 1, rp);
	update(p);
}
void change(int p, int lp, int rp, int l, int r, ll k) {
	if(l <= lp && rp <= r) {
		sum[p] += (rp - lp + 1) * k;
		tag[p] += k;
		return ;
	}
	int mid = (lp + rp) >> 1;
	if(tag[p]) spread(p, mid - lp + 1, rp - mid);
	if(l <= mid) change(p<<1, lp, mid, l, r, k);
	if(r > mid) change(p<<1|1, mid + 1, rp, l, r, k);
	update(p);
}

ll qry(int p, int lp, int rp, int l, int r) {
	if(l <= lp && rp <= r) return sum[p];
	int mid = (lp + rp) >> 1;
	if(tag[p]) spread(p, mid - lp + 1, rp - mid);
	ll ans = 0;
	if(l <= mid) ans += qry(p<<1, lp, mid, l, r);
	if(r > mid) ans += qry(p<<1|1, mid+1, rp, l, r);
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m, op, x, y, k;
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	build(1, 1, n);
	while(m--) {
		cin >> op >> x >> y;
		if(op == 1) {
			cin >> k;
			change(1, 1, n, x, y, k);
		} else {
			cout << qry(1, 1, n, x, y) << '\n';
		}
	}
	return 0;
}

评测结果