段树简介

假设我们有一个数组:

+-------+-----+-----+-----+-----+-----+-----+
| `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) 空间来维护它,并且它会在时间上回答一个查询。

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

StackOverflow 文档

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

StackOverflow 文档

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

StackOverflow 文档

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

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

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

  • [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 个最小元素
  • 查找无序对的数量