段树简介

假设我们有一个数组：

+-------+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |
+-------+-----+-----+-----+-----+-----+-----+
| `Value` |  -1 |  3  |  4  |  0  |  2  |  1  |
+-------+-----+-----+-----+-----+-----+-----+

我们想对这个数组执行一些查询。例如：

• index- 2 到 index- 4 的最小值是多少？ - > 0
• index- 0 到 index- 3 的最大值是多少？ - > 4
• 从 index- 1 到 index- 5 的总和是多少？ - > 10

我们怎么找到它？

蛮力：
我们可以遍历数组从起始索引到完成索引并回答我们的查询。在这种方法中，每个查询都需要 O(n) 时间，其中 n 是起始索引和结束索引之间的差异。但是，如果有数百万的数字和数百万的查询呢？对于 m 个查询，需要时间。因此，对于我们数组中的 10⁵值，如果我们进行 10⁵查询，对于最坏情况，我们需要遍历 10 个项目。

动态编程：
我们可以创建一个 6X6 矩阵来存储不同范围的值。对于范围最小查询（RMQ），我们的数组看起来像：

              0     1     2     3     4     5
     +-----+-----+-----+-----+-----+-----+-----+
     |     |  -1 |  3  |  4  |  0  |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  0  |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |
     +-----+-----+-----+-----+-----+-----+-----+
  1  |  3  |     |  3  |  3  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  2  |  4  |     |     |  4  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  3  |  0  |     |     |     |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  4  |  2  |     |     |     |     |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  5  |  1  |     |     |     |     |     |  1  |
     +-----+-----+-----+-----+-----+-----+-----+

一旦我们有了这个矩阵构建，就足以回答所有的 RMQ。这里， Matrix [i] [j] 将索引 -i 的最小值存储到 index- j 。例如：从 index- 2 到 index- 4 的最小值是 Matrix [2] [4] = 0 。这个矩阵在 O(1) 时间内回答查询，但是需要 O（n²） 时间来构建这个矩阵和 O(n²) 空间来存储它。因此，如果 n 是一个非常大的数字，那么它的扩展性不是很好。

段树：
一个线段树是用于存储间隔，或段树数据结构。它允许查询哪些存储的段包含给定的点。构建一个分段树需要花费时间，它需要 O(n) 空间来维护它，并且它会在时间上回答一个查询。

段树是二叉树，给定数组的元素将是该树的叶子。我们将通过将数组分成两半来创建分段树，直到我们到达单个元素。所以我们的部门会为我们提供：

现在，如果我们用叶子的最小值替换非叶子节点，我们得到：

所以这是我们的分段树。我们可以注意到，根节点包含整个数组的最小值（范围[0,5]），其左子节点包含左数组的最小值（范围[0,2]），右子节点包含最小值我们的右数组的值（范围[3,5]）等等。叶节点包含每个单独点的最小值。我们得到：

现在让我们在这棵树上做一个范围查询。要进行范围查询，我们需要检查三个条件：

• 部分重叠：我们检查两个叶子。
• 总重叠：我们返回存储在节点中的值。
• 没有重叠：我们返回一个非常大的值或无穷大。

假设我们想检查范围 [2,4] ，这意味着我们想要找到从索引 2 到 4 的最小值。我们将从根开始，检查节点中的范围是否与查询范围重叠。这里，

• [2,4] 不完全重叠 [0,5] 。所以我们会检查两个方向。
  • 在左子树， [2,4] 部分重叠 [0,2] 。我们会检查两个方向。
    • 在左子树， [2,4] 不重叠 [0,1] ，所以这不会有助于我们的答案。我们回归无限。
    • 在右子树， [2,4] 完全重叠 [2,2] 。我们返回 4 。
      这两个返回值（4，无穷大）中的最小值为 4 。我们从这部分得到 4 分。
  • 在右子树， [2,4] 部分重叠。所以我们会检查两个方向。
    • 在左子树， [2,4] 完全重叠 [3,4] 。我们返回 0 。
    • 在右子树， [2,4] 不重叠 [5,5] 。我们回归无限。
      这两个返回值（0，无穷大）中的最小值为 0 。我们从这部分得到 0 。
• 返回值(4,0)的最小值为 0 。这是我们期望的最小范围 [2,4] 。

现在我们可以检查一下，无论我们的查询是什么，最多需要 4 个步骤才能从这个分段树中找到所需的值。

使用：

• 范围最小查询
• 最低的共同祖先
• 懒惰的传播
• 动态子树总和
• 忽视和最小
• 双场
• 找到第 k 个最小元素
• 查找无序对的数量