题目链接： 传送门
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 500010; int m, p, arr[N]; char op[10]; //结构体 struct Node { int l, r; int sum; } tr[N * 4]; //pushup更新 void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } //创建线段树 void build(int u, int l, int r) { //只指向了一个点 if (l == r) { tr[u] = {l, r, arr[l]}; //不断往下二分 } else { tr[u].l = l, tr[u].r = r; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } //查询区间和 int query(int u, int l, int r) { //当前区间是查询区间的子集 if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum; else { int mid = tr[u].l + tr[u].r >> 1; //查询区间在当前区间的左边 if (r <= mid) { return query(u << 1, l, r); //查询区间在当前区间的右边 } else if (l > mid) { return query(u << 1 | 1, l, r); //查询区间在当前区间的两边 } else { int left = query(u << 1, l, r); int right = query(u << 1 | 1, l, r); return left + right; } } } //修改相应点的值 void modify(int u, int x, int val) { if (tr[u].l == x && tr[u].r == x) tr[u].sum = val; else { int mid = tr[u].l + tr[u].r >> 1; //查询到当前点在左边 if (x <= mid) modify(u << 1, x, val); //查询到当前点在右边 else modify(u << 1 | 1, x, val); pushup(u); } } int main() { int t, n, num1, num2, ca = 1; scanf("%d", &t); while(t--) { memset(tr, 0, sizeof(tr)); memset(arr, 0, sizeof(arr)); scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &arr[i]); //创建线段树 build(1, 1, n); printf("Case %d:\n",ca++); //读入操作 while(scanf("%s", op)) { //结束 if(op[0] == 'E') break; //查询 else if(op[0] == 'Q') { scanf("%d%d", &num1, &num2); printf("%d\n", query(1, num1, num2)); //增添 } else if(op[0] == 'A') { scanf("%d%d", &num1, &num2); arr[num1] += num2; modify(1, num1, arr[num1]); //删减 } else { scanf("%d%d", &num1, &num2); arr[num1] -= num2; modify(1, num1, arr[num1]); } } } }这是一道线段树单点查询，区间修改的题目，线段树相关知识详情请见某大佬博客 这道题的基本思路就是维护一个求总和的线段树，显然pushup的更新方法此时就应该是tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum 即让父结点的值等于两个子节点的和，区间查询时，遇到分叉点则分别求两个分叉，再返回两个分叉的总和，其余的套模板就好，记得初始化的问题。
