kuangbin 专题七：线段树 敌兵布阵

题目链接：
传送门

#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 即让父结点的值等于两个子节点的和，区间查询时，遇到分叉点则分别求两个分叉，再返回两个分叉的总和，其余的套模板就好，记得初始化的问题。