线段树 - 范围最小值查询

在上篇文章中，我们通过一个简单的例子介绍了线段树。本文将介绍线段树的另一个应用，即区间最值查询问题。我们要解决的问题如下：

我们有一个数组 arr[0, 1, n]。其中 0 = qs = qe = n-1，我们应该能够高效地找出索引 qs（查询开始）到 qe（查询结束）之间的最小值，其中 0 <= qs <= qe <= n-1。

通过遍历 qs 到 qe 的循环来找出给定范围内的最小元素是一个简单的解决方案。在最坏的情况下，这种解决方案需要 O(n) 的时间。

另一种方法是创建一个二维数组，其中条目 I j] 保存范围 arr[i..j] 中的最小值。预处理需要 O(n2) 的时间，但现在可以在 O(1) 时间内找出给定范围的最小值。此外，此方法需要 O(n2) 的额外空间，这对于大型输入数组来说可能非常昂贵。

使用线段树可以快速地进行查询和预处理。使用线段树进行预处理的时间复杂度为 O(n)，而区间最值查询的时间复杂度为 O(Logn)。线段树所需的额外存储空间为 O(n)。

线段树表示

• 输入数组的元素被称为叶节点。
• 每个内部节点都表示其下方至少有一个叶子节点。

线段树显示为树的数组表示。索引为 I 的每个节点的左子节点位于索引 2*i+1，右子节点位于索引 2*i+2，父节点位于索引( I - 1) / 2。

从数组构建线段树

我们首先检查线段 arr[0,... n-1]。当前线段每次都被分成两半（假设它还没有变成长度为 1 的线段），然后对两个半部分执行相同的操作，并将每个线段的最小值存储在线段树节点中。

除了最后一层，创建的线段树的每一层都将是完全填充的。此外，由于我们在每一层都始终将线段分成两半，因此该树将是一个满二叉树。由于创建的树总是带有 n 个叶子节点的满二叉树，因此将有 n-1 个内部节点。因此，总共有 2*n - 1 个节点。

线段树的高度将为 log2n。考虑到树是使用数组表示的，并且必须保留父子索引之间的关系，因此将为线段树分配 2 * 2 log2n - 1 的内存。

找出指定范围的最小值。

一旦构建了线段树，如何使用它进行区间最值查询。查找最小值的算法如下。

C++ 代码

上述策略的应用如下所示：

输出

Minimum of values in range [1, 5] is = 2

• 时间复杂度：树的创建具有 O(n) 的时间复杂度。总共有 2n-1 个节点，并且树的创建过程只计算每个节点的值一次。
  查询的时间复杂度为 O(Logn)。我们在每个级别最多处理两个节点来查询区间最小值，并且总级别数为 O(Logn)。
• 辅助空间：已占用 n 的额外空间，因此，O(N)