思想：访问到树中结点时不再下降，查询时再更新。
const int N = 1e5 + 5; int t; int w[N]; struct node { int l, r; ll sum, add; }tr[4*N]; void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } void pushdown(int u) { node &root = tr[u], &le = tr[u << 1], &re = tr[u << 1 | 1]; if (root.add) { le.add += root.add, le.sum += (ll)(le.r - le.l + 1)*root.add; re.add += root.add, re.sum += (ll)(re.r - re.l + 1)*root.add; root.add = 0; } } void build(int u, int l, int r) { if (l == r)tr[u] = { l,r,w[l],0 }; else { tr[u] = { l,r }; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } void modify(int u, int l, int r, int d) { if (tr[u].l >= l && tr[u].r <= r)//树中结点,不往下走了，查询时再递归 { tr[u].sum += (ll)(tr[u].r - tr[u].l + 1)*d; tr[u].add += d; } else { pushdown(u);//往下走，需要递归 int mid = tr[u].l + tr[u].r >> 1; if (l <= mid)modify(u << 1, l, r, d); if (r > mid)modify(u << 1 | 1, l, r, d); pushup(u); } } ll query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r)return tr[u].sum; //往下走,分裂时用父节点更新子节点 pushdown(u); int mid = tr[u].l + tr[u].r >> 1; ll sum = 0; if (l <= mid)sum += query(u << 1, l, r); if (r > mid)sum += query(u << 1 | 1, l, r); return sum; } int main() { // freopen("in.txt", "r", stdin); int n, m; scanf("%d%d", &n, &m); f(i, 1, n)scanf("%d", &w[i]); string op; int l, r, d; build(1, 1, n); while (m--) { cin >> op; scanf("%d %d", &l, &r); if (op == "C") { scanf("%d", &d); modify(1, l, r, d); } else printf("%lld\n", query(1,l,r)); } return 0; }