この問題は Range Add Range Sum Query という名前で知られています。

この問題は Fenwick Tree を \(2\) 本持つ解法も存在しますが、ここではより汎用的な Lazy Segment Tree を用いた解法を紹介します。

以下では AtCoder Library の Lazy Segtree に基づき説明します。

Lazy Segtree ではモノイドの型 \(S\) と \(S\) から \(S\) への関数写像の集合 \(F\) を定義する必要があります。ここでは、 \(S\) で区間の値の総和と長さを保持する（それぞれ \(v,l\) とする）ことにし、 \(F\) では倍率 \(f\) を用意し \((v,l) \in S,\ f \in F\) に対し \(f((v,l))=(v+fl,l)\) とし、 \(f,g\in F\) に対し \(f\circ g=f+g\) として定義します。

このように \(S,F\) を定義するとこれらは Lazy Segtree の要件を満たしていることが分かります。さらに、Range Add クエリでは区間に関数 \(f\) を作用させ、 Range Sum クエリでは区間全てのモノイドの総積を求めれば良いです。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N+Q\log N)\) になります。

実装例(C++)

#include <atcoder/lazysegtree>
#include <bits/stdc++.h>
using namespace std;
struct S {
	long value;
	int size;
};
using F = long;
S op(S a, S b) { return {a.value + b.value, a.size + b.size}; }
S e() { return {0, 0}; }
S mapping(F f, S x) { return {x.value + f * x.size, x.size}; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }
int main() {
	int n, q;
	cin >> n >> q;
	vector<S> to_seg(n);
	for (int i = 0; i < n; i++) {
		long ci;
		cin >> ci;
		to_seg[i] = {ci, 1};
	}
	atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(to_seg);
	while (q--) {
		int ty;
		cin >> ty;
		if (ty == 1) {
			int l, r;
			long v;
			cin >> l >> r >> v;
			l--;
			seg.apply(l, r, v);
		} else {
			int l, r;
			cin >> l >> r;
			l--;
			cout << seg.prod(l, r).value << endl;
		}
	}
}