我们在前一篇文章中，通过一个简单的例子介绍了线段树。在这篇文章中，我们将讨论<a href="https://en.wikipedia.org/wiki/RangeMinimumQuery">区间最小值查询问题，这是线段树应用的另一个典型案例。以下是问题的具体陈述：
我们有一个数组 arr[0 . . . n-1]。我们需要能够高效地找到从索引 qs（查询起始）到 qe （查询结束）之间的最小值，其中 0 <= qs <= qe <= n-1。
一种简单的方法是运行一个从 qs 到 qe 的循环，以找到给定范围内的最小元素。在最坏的情况下，这种解法需要 O(n) 的时间。
另一种解法是创建一个二维数组，其中条目 INLINECODE72ff28d1 存储范围 INLINECODE2a30c3cc 内的最小值。现在可以在 O(1) 时间内计算给定范围的最小值，但预处理需要 O(n2) 时间。此外，这种方法需要 O(n2) 的额外空间，对于大型输入数组来说，这可能会变得非常巨大。
线段树可以在适度的时间内进行预处理和查询。使用线段树，预处理时间为 O(n)，而范围最小值查询的时间复杂度为 O(log n)。所需的额外空间为 O(n)，用于存储线段树。
线段树的表示
> 1. 叶子节点是输入数组的元素。
> 2. 每个内部节点代表其所有子叶子节点的最小值。
我们使用树的数组表示法来表示线段树。对于索引 INLINECODE47c61bb9 处的每个节点，左子节点位于索引 INLINECODE03a3c0e8，右子节点位于 (2 * i + 2)，父节点位于 (i – 1) / 2
从给定数组构造线段树
> 我们从数组段 arr[0 . . . n-1] 开始。每次我们将当前段分成两半（如果它还没有成为长度为 1 的段），然后对两半都调用相同的过程，对于每个这样的段，我们将最小值存储在一个线段树节点中。
构造的线段树的所有层都将被完全填充，除了最后一层。此外，该树将是一棵<a href="https://en.wikipedia.org/wiki/Binarytree#Typesofbinarytrees">满二叉树，因为我们总是在每一层将段分成两半。由于构造的树始终是具有 n 个叶子的满二叉树，因此将有 n – 1 个内部节点。所以节点总数将是 2 * n – 1。
线段树的高度将是 ?log?n?。由于树是使用数组表示的，并且必须维护父索引和子索引之间的关系，因此为线段树分配的内存大小将是 2 2?log2n? – 1*。
查询给定范围的最小值
> 一旦树被构造完成，如何使用构造好的线段树进行范围最小值查询？以下是获取最小值的算法。
>
> // qs–> 查询起始索引, qe –> 查询结束索引
> int RMQ(node, qs, qe) {
> if 节点的范围完全在 qs 和 qe 之内
> return 节点中的值
> else if 节点的范围完全在 qs和 qe 之外
> return INFINITE (无限大)
> else
> return min ( RMQ(节点的左孩子, qs, qe), RMQ (节点的右孩子, qs, qe) )
> }
C++
`
// C++ program for range minimum
// query using segment tree
#include
using namespace std;
// A utility function to get minimum of two numbers
int minVal(int x, int y) {
return (x Pointer to segment tree
// index --> Index of current node in the tree
// ss & se --> Starting and ending indexes
// qs & qe --> Starting and ending indexes of query range
int RMQUtil(vector &st, int ss, int se, int qs,
int qe, int index) {
// If segment of this node is a part of given range
// then return the min of the segment
if (qs = se)
return st[index];
// If segment of this node if outside the range
if (se qe)
return INT_MAX;
// If a part of this segment
// overlaps with the given range
int mid = getMid(ss, se);
return minVal(RMQUtil(st, ss, mid, qs, qe, 2*index+1),
RMQUtil(st, mid+1, se, qs, qe, 2*index+2));
}
// Return minimum of elements in range
// from index qs to qe
int RMQ(vector &st, int n, int qs, int qe) {
// Check for invalid input
if (qs n-1 || qs > qe) {
cout << "Invalid Input";
return -1;
}
return RMQUtil(st, 0, n-1, qs, qe, 0);
}
// A recursive function that constructs
// Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(vector &arr, int ss, int se,
vector &st, int si) {
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se) {
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the minimum of two values in this node
int mid = getMid(ss, se);
st[si] = minVal(constructSTUtil(arr, ss, mid, st, si*2+1),
constructSTUtil(arr, mid+1, se, st, si*2+2));
return st[si];
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
vector constructST(vector &arr, int n) {
// Allocate memory for segment tree
// Height of segment tree
int x = (int)(ceil(log2(n)));
// Maximum size of segment tree
int max_size = 2*(int)pow(2, x) - 1;
vector st(max_size);
// Fill the allocated memory st
constructSTUtil(arr, 0, n-1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver program to test above functions
int main() {
vector arr = {1, 3, 2, 7, 9, 11};
int n = arr.size();
// Build segment tree from given array
vector st = constructST(arr, n);
int qs = 1; // Starting index of query range
int qe = 5; // Ending index of query range
// Print minimum value in arr[qs..qe]
cout << "Minimum of values in range [" << qs << ", " << qe
<< "] is = " << RMQ(st, n, qs, qe) << endl;
return 0;
}