本文共 2705 字，大约阅读时间需要 9 分钟。
线段树是解决区间查询问题的高效数据结构，特别适用于动态查询区域内的最大值和最小值。在本文中，我们将使用线段树来处理每个查询请求，找到区间内的最大值与最小值之差。
线段树的每个节点表示一个区间，该区间内的所有节点都具有相同的性质（在本例中，最大值和最小值）。每个节点包含以下信息：
线段树的构建采用递归的方法，具体步骤如下：
插入数据时，我们需要将一个新的值插入到线段树中，并更新相关节点的最大值和最小值。具体步骤如下：
查询操作需要找到区间内的最大值和最小值。具体步骤如下：
#include#include #include using namespace std;#define N 50050#define INF 0x3fffffffstruct node { int b, d; int mx, mi; node* Tl; node* Tr;};int cnt;node* Tbuild(int s, int t) { node* tmp = &edge[cnt++]; tmp->mi = INF; tmp->mx = -1; tmp->Tl = tmp->Tr = NULL; tmp->b = s; tmp->d = t; int mid = (s + t) / 2; if (s != t) { tmp->Tl = Tbuild(s, mid); tmp->Tr = Tbuild(mid + 1, t); } return tmp;}void insert(node* tmp, int s, int k) { if (s > tmp->mx) { tmp->mx = s; } if (s < tmp->mi) { tmp->mi = s; } if (tmp->b == tmp->d && tmp->d == k) { return; } int mid = (tmp->b + tmp->d) / 2; if (k <= mid) { insert(tmp->Tl, s, k); } else { insert(tmp->Tr, s, k); }}int findmx(node* tmp, int s, int t) { if (tmp->b == s && tmp->d == t) { return tmp->mx; } int mid = (tmp->b + tmp->d) / 2; if (s > mid) { return findmx(tmp->Tr, max(mid + 1, s), t); } if (t <= mid) { return findmx(tmp->Tl, s, min(mid, t)); } return max(findmx(tmp->Tl, s, mid), findmx(tmp->Tr, mid + 1, t));}int findmi(node* tmp, int s, int t) { if (tmp->b == s && tmp->d == t) { return tmp->mi; } int mid = (tmp->b + tmp->d) / 2; if (s > mid) { return findmi(tmp->Tr, max(mid + 1, s), t); } if (t <= mid) { return findmi(tmp->Tl, s, min(mid, t)); } return min(findmi(tmp->Tl, s, mid), findmi(tmp->Tr, mid + 1, t));}int main() { cnt = 0; scanf("%d%d", &n, &q); head = Tbuild(1, n); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); insert(head, x, i); } for (int i = 0; i < q; i++) { int A, B; scanf("%d%d", &A, &B); int max_val = findmx(head, A, B); int min_val = findmi(head, A, B); cout << (max_val - min_val) << endl; }}
这个代码实现了一个线段树，用于高效处理区间查询问题。通过线段树，我们能够在O(log N)的时间复杂度内找到任意区间内的最大值和最小值，从而快速响应每个查询请求。这种方法特别适用于大规模数据和大量查询的情况，能够显著提高处理效率。
转载地址：http://ifxfk.baihongyu.com/