题目： 传送门 改进： 相较于单点更新，引入lazy数组，lazy[node] = val表示当前节点（node）维护的子区间全部都要加上val（可正可负）。lazy标记在区间更新和区间查询时下传（push_down） Code：
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <vector> #include <map> #include <queue> #include <algorithm> using namespace std; typedef long long ll; typedef pair<int, int> P; const int inf = 0x3f3f3f3f; const int maxn = 1000007; int arr[maxn]; ll tree[4*maxn]; ll lazy[4*maxn]; int n, q; void push_down(int node, int m) { if (lazy[node]) { lazy[2*node] += lazy[node]; lazy[2*node+1] += lazy[node]; tree[2*node] += lazy[node] * (m - m/2); tree[2*node+1] += lazy[node] * (m/2); lazy[node] = 0; } } void push_up(int node) { tree[node] = tree[2*node] + tree[2*node+1]; } void build_tree(int node, int l, int r) { if (l == r) { tree[node] = arr[l]; return; } lazy[node] = 0; int mid = (l + r) / 2; build_tree(2*node, l, mid); build_tree(2*node+1, mid+1, r); push_up(node); } ll query_tree(int node, int l, int r, int fl, int fr) { if (l == fl && r == fr) { return tree[node]; } push_down(node, r - l + 1); int mid = (l + r) / 2; if (fr <= mid) { return query_tree(2*node, l, mid, fl, fr); } else if (mid < fl) { return query_tree(2*node+1, mid+1, r, fl, fr); } else { return query_tree(2*node, l, mid, fl, mid) + query_tree(2*node+1, mid+1, r, mid+1, fr); } } void add_tree(int node, int l, int r, int tl, int tr, int val) { if (l == tl && r == tr) { lazy[node] += val; tree[node] += (r - l + 1) * val; return; } push_down(node, r - l + 1); int mid = (l + r) / 2; if (tr <= mid) { add_tree(2*node, l, mid, tl, tr, val); } else if (tl > mid) { add_tree(2*node+1, mid+1, r, tl, tr, val); } else { add_tree(2*node, l, mid, tl, mid, val); add_tree(2*node+1, mid+1, r, mid+1, tr, val); } push_up(node); } int main() { scanf("%d %d", &n, &q); for (int i=1;i<=n;i++) { scanf("%d", &arr[i]); } build_tree(1, 1, n); char op; int a, b, c; while (q--) { scanf(" %c", &op); if (op == 'Q') { scanf("%d %d", &a, &b); printf("%lld\n", query_tree(1, 1, n, a, b)); } else if (op == 'C') { scanf("%d %d %d", &a, &b, &c); add_tree(1, 1, n, a, b, c); } } return 0; }