使用线段树时需要根据实际情况修改线段树模板
#include <iostream>
#include <vector>
using namespace std;
#define int long long
class SegTree {
public:
struct Node { int l, r, sum, add; };
vector<int> a;
vector<Node> stree;
int n;
SegTree(int n) : a(n + 10), stree(4 * n + 10) { this->n = n; }
void pushup(int u) { stree[u].sum = stree[u << 1].sum + stree[u << 1 | 1].sum; }
void pushdown(int u) {
Node& l = stree[u << 1], &r = stree[u << 1 | 1], &rt = stree[u];
l.sum += (l.r - l.l + 1) * rt.add; r.sum += (r.r - r.l + 1) * rt.add;
l.add += rt.add; r.add += rt.add; rt.add = 0;
}
void input() { for (int i = 1; i <= n; i++) cin >> a[i]; build(1, n, 1); }
void build(int l, int r, int u) {
if (l >= r) { stree[u] = { l, r, a[l], 0 }; return; }
stree[u] = { l, r, 0, 0 };
int mid = l + r >> 1;
build(l, mid, u << 1); build(mid + 1, r, u << 1 | 1);
pushup(u);
}
int query(int l, int r, int u) {
if (l <= stree[u].l && r >= stree[u].r) return stree[u].sum;
pushdown(u);
int mid = stree[u].l + stree[u].r >> 1, res = 0;
if (l <= mid) res += query(l, r, u << 1);
if (r > mid) res += query(l, r, u << 1 | 1);
return res;
}
void modify(int l, int r, int d, int u) {
if (stree[u].l >= l && stree[u].r <= r) {
stree[u].add += d;
stree[u].sum += (stree[u].r - stree[u].l + 1) * d;
return;
}
pushdown(u);
int mid = stree[u].l + stree[u].r >> 1;
if (l <= mid) modify(l, r, d, u << 1);
if (r > mid) modify(l, r, d, u << 1 | 1);
pushup(u);
}
};
signed main() {
int n, m;
cin >> n >> m;
SegTree tr(n);
tr.input();
while (m--) {
char c;
cin >> c;
if (c == 'Q') {
int l, r;
cin >> l >> r;
cout << tr.query(l, r, 1) << endl;
}
else {
int l, r, d;
cin >> l >> r >> d;
tr.modify(l, r, d, 1);
}
}
return 0;
}