线段树
模版代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100010], d[400010], tag[400010];
inline void push_up(int p) {
d[p] = d[p * 2] + d[p * 2 + 1];
}
inline void push_down(int s, int t, int p) {
int mid = (s + t) >> 1;
if (tag[p]) {
d[p * 2] += tag[p] * (mid - s + 1);
d[p * 2 + 1] += tag[p] * (t - mid);
tag[p * 2] += tag[p], tag[p * 2 + 1] += tag[p];
}
tag[p] = 0;
}
inline void build(int s, int t, int p) {
if (s == t) {
d[p] = a[s];
return;
}
int mid = (s + t) >> 1;
build(s, mid, p * 2), build(mid + 1, t, p * 2 + 1);
push_up(p);
}
inline void update(int l, int r, int c, int s, int t, int p) {
if (l <= s && r >= t) {
d[p] += (t - s + 1) * c, tag[p] += c;
return;
}
int mid = (s + t) >> 1;
push_down(s, t, p);
if (l <= mid) update(l, r, c, s, mid, p * 2);
if (r > mid) update(l, r, c, mid + 1, t, p * 2 + 1);
push_up(p);
}
inline int getsum(int l, int r, int s, int t, int p) {
if (l <= s && t <= r) {
return d[p];
}
int mid = (s + t) >> 1;
push_down(s, t, p);
int sum = 0;
if (l <= mid) sum += getsum(l, r, s, mid, p * 2);
if (r > mid) sum += getsum(l, r, mid + 1, t, p * 2 + 1);
return sum;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m, op, l, r, k;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, n, 1);
while (m--) {
cin >> op;
if (op == 1) {
cin >> l >> r >> k;
update(l, r, k, 1, n, 1);
}else {
cin >> l >> r;
cout << getsum(l, r, 1, n, 1) << "\n";
}
}
return 0;
}