题目链接： 传送门
#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 dif; int hest; int sest; } tr[N * 4]; //更新操作 void pushup(Node &u, Node &l, Node &r) { u.hest = max(l.hest, r.hest); u.sest = min(l.sest, r.sest); u.dif = u.hest - u.sest; } //重载更新某点 void pushup(int u) { pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); } //创建线段树 void build(int u, int l, int r) { if (l == r) { tr[u] = {l, r, 0, arr[l], 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); } } //查询操作 Node query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) return tr[u]; 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 { Node left = query(u << 1, l, r); Node right = query(u << 1 | 1, l, r); Node ans; pushup(ans, left, right); return ans; } } } int main() { int m, n, s, e; 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("%d%d", &s, &e); printf("%d\n",query(1, s, e).dif); } } }这是一道线段树单点修改区间查询的一道题目，关于线段树的知识详情请见某大佬博客 这个道题是用线段树来维护区间最大差值的一道题，是这道题的pushup操作主要是把一个父结点来存储两个子节点中的最大点最小点即差都记下来，查询时遇到分支，则求出两个分叉的分别的找两个点的最大和最小点并返回，同时计算差值，其余的操作与就和普通模板差不多了。
