1，构建线段树
void build(int node, int start, int end) {if(start == end) {tree[node] = arr[start];} else {int mid = (start + end) / 2;build(2 * node, start, mid);build(2 * node + 1, mid + 1, end);tree[node] = tree[2 * node] + tree[2 * node + 1];}
}2，区间查询
int query(int node, int start, int end, int l, int r) {updatelazy(node, start, end); // 确保本节点的值是最新的if (r < start || l > end) return 0; // 当前区间与查询区间无交集if (l <= start && end <= r) return tree[node]; // 当前区间完全包含在查询区间内int mid = (start + end) / 2;return query(2 * node, start, mid, l, r) + query(2 * node + 1, mid + 1, end, l, r);
}3，单点更新
void adddate(int node, int start, int end, int index, int val) {if(start == end) {arr[index] = val;tree[node] = val;} else {int mid = (start + end) / 2;if(index >= start && index <= mid) {adddate(2 * node, start, mid, index, val);} else {adddate(2 * node + 1, mid + 1, end, index, val);}tree[node] = tree[2 * node] + tree[2 * node + 1];}
}
4，区间更新
void update(int node, int start, int end, int l, int r, int val) {updatelazy(node, start, end); // 处理本节点的懒标记if (r < start || l > end) return; // 当前区间与更新区间无交集if (l <= start && end <= r) {tree[node] += (end - start + 1) * val;if (start != end) {lazy[2 * node] += val;lazy[2 * node + 1] += val;}return;}int mid = (start + end) / 2;update(2 * node, start, mid, l, r, val);update(2 * node + 1, mid + 1, end, l, r, val);tree[node] = tree[2 * node] + tree[2 * node + 1];
}5，处理懒标记
void updatelazy(int node, int start, int end) {if (lazy[node] != 0) {// 更新当前区间的和，lazy[node]是需要加的值tree[node] += (end - start + 1) * lazy[node];if (start != end) {// 将懒标记传递给子节点lazy[2 * node] += lazy[node];lazy[2 * node + 1] += lazy[node];}// 清除当前节点的懒标记lazy[node] = 0;}
}
int main() {int n, m;cin >> n >> m;for(int i = 1; i <= n; i++) {cin >> arr[i];}build(1, 1, n);for(int i = 0; i < m; i++) {char s;int x, y, z;cin >> s;if (s == 'Q') {cin >> x >> y;cout << query(1, 1, n, x, y) << endl;} else if (s == 'C') {cin >> x >> y >> z;update(1, 1, n, x, y, z);} else if (s == 'D') {cin >> x >> y;adddate(1, 1, n, x, y);}}return 0;
}