题目链接： 传送门
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 500010; int m, p, arr[N]; struct Node { int l, r; int max; } tr[N * 4]; //更新操作 void pushup(int u) { tr[u].max = max(tr[u << 1].max, tr[u << 1 | 1].max); } //创建线段树 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].max; 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 max(left, right); } } } //修改某点的值 void modify(int u, int x, int val) { if (tr[u].l == x && tr[u].r == x) tr[u].max = 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 m, n, s, e; char op; //注意本题有多个测试实例 while(scanf("%d%d", &n, &m) != EOF) { for(int i = 1; i <= n; i++) scanf("%d", &arr[i]); //创建线段树 build(1, 1, n); for(int i = 1; i <= m; i++) { scanf(" %c%d%d", &op, &s, &e); //判断操作类型 if(op == 'Q') { printf("%d\n",query(1, s, e)); } else { modify(1, s, e); } } } }这是一道线段树单点修改区间查询的一道题目，关于线段树的知识详情请见某大佬博客 这个道题是用线段树来维护区间最大值的一道题，是这道题的pushup操作主要是把一个父结点来存储两个子节点的最大值，查询时遇到分支，则找到两个分叉的最大值，其余的操作与就和普通模板差不多了，使用scanf注意格式。
