【译】Swift算法俱乐部-线段树

2019-07-17 本文已影响0人 Andy_Ron

Swift算法俱乐部

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Segment Tree

线段树（Segment Tree）

有关懒惰传播的示例，请参阅此文章。

我很高兴向您介绍线段树（Segment Tree）。它实际上是我最喜欢的数据结构之一，因为它非常灵活且实现简单。

假设你有一个某种类型的数组a和一些关联函数f。例如，函数可以是求和，乘法，最小，最大，最大公约数等。

你的任务是：

回答由l和r给出的间隔的查询，即执行 f(a[l], a[l+1], ..., a[r-1], a[r])
支持替换某个索引的一个项目a[index] = newItem

例如，如果我们有一个数字数组：

var a = [ 20, 3, -1, 101, 14, 29, 5, 61, 99 ]

我们想查询这个数组3到7区间，并执行函数"sum"。这意味着我们执行以下操作：

101 + 14 + 29 + 5 + 61 = 210

因为101在数组的索引3处，而61在索引7处。所以我们将101和61之间的所有数字传递给sum函数，这将它们全部加起来。如果我们使用了“min”函数，结果将为5，因为这是3到7之间的最小数字。

如果我们的数组的类型是Int并且f只是两个整数的求和，这是原始的方法：

func query(array: [Int], l: Int, r: Int) -> Int {
  var sum = 0
  for i in l...r {
    sum += array[I]
  }
  return sum
}

在最坏的情况下，该算法的运行时间为O(n)，即当l = 0, r =n-1（其中n是数组的元素数量）。如果我们有m次查询，我们得到O(m*n)复杂度。

如果我们有一个包含100,000个项的数组(n = 10^5并且我们必须执行100个查询 (m = 100)，那么我们的算法将执行 10^7单位工作。哎哟，这听起来不太好。让我们来看看我们如何改进它。

线段树允许我们应答查询并用 O(log n)时间替换。这不是魔术吗？✨

线段树的主要思想很简单：我们预先计算数组中的一些段，然后我们可以使用它们而不重复计算。

线段树的结构

线段树只是一个二叉树，其中每个节点都是SegmentTree类的一个实例：

public class SegmentTree<T> {
  private var value: T
  private var function: (T, T) -> T
  private var leftBound: Int
  private var rightBound: Int
  private var leftChild: SegmentTree<T>?
  private var rightChild: SegmentTree<T>?
}

每个节点都有以下数据：

leftBound和rightBound 描述了一个间隔
leftChild和rightChild 是指向子节点的指针
value是函数 f(a[leftBound], a[leftBound+1], ..., a[rightBound-1], a[rightBound]) 的结果。

如果我们的数组是[1, 2, 3, 4]，函数 f = a + b ，则线段树看起来像这样：

structure

每个节点的leftBound和rightBound标记为红色。

构建线段树

以下是我们如何创建线段树的节点：

public init(array: [T], leftBound: Int, rightBound: Int, function: @escaping (T, T) -> T) {
    self.leftBound = leftBound
    self.rightBound = rightBound
    self.function = function

    if leftBound == rightBound {                    // 1
      value = array[leftBound]
    } else {
      let middle = (leftBound + rightBound) / 2     // 2

      // 3
      leftChild = SegmentTree<T>(array: array, leftBound: leftBound, rightBound: middle, function: function)
      rightChild = SegmentTree<T>(array: array, leftBound: middle+1, rightBound: rightBound, function: function)

      value = function(leftChild!.value, rightChild!.value)  // 4
    }
  }

请注意，这是一个递归方法。你给它一个数组，如[1, 2, 3, 4]，它构建整个树，从根节点到所有子节点。

如果leftBound和rightBound相等，则递归终止。这样的SegmentTree实例表示叶节点。对于输入数组[1,2,3,4]，这个过程将创建四个这样的叶节点：1，2，3和4。我们只用数组中的数字填充value属性。
但是，如果rightBound仍然大于leftBound，我们创建两个子节点。我们将当前段划分为两个相等的段（至少，如果长度是偶数;如果它是奇数，则一个段将略大）。
递归地为这两个段构建子节点。左子节点覆盖区间[leftBound, middle]，右子节点覆盖[middle + 1, rightBound]。
在构造了我们的子节点之后，我们可以计算自己的值，因为f(leftBound, rightBound) = f(f(leftBound, middle), f(middle+1, rightBound))。这是数学！

构建这个树的操作是O(n)。

获得查询结果

我们经历了所有这些麻烦，因此我们可以有效地查询树。

代码：

  public func query(withLeftBound: leftBound: Int, rightBound: Int) -> T {
    // 1
    if self.leftBound == leftBound && self.rightBound == rightBound {
      return self.value
    }

    guard let leftChild = leftChild else { fatalError("leftChild should not be nil") }
    guard let rightChild = rightChild else { fatalError("rightChild should not be nil") }

    // 2
    if leftChild.rightBound < leftBound {
      return rightChild.query(withLeftBound: leftBound, rightBound: rightBound)

    // 3
    } else if rightChild.leftBound > rightBound {
      return leftChild.query(withLeftBound: leftBound, rightBound: rightBound)

    // 4
    } else {
      let leftResult = leftChild.query(withLeftBound: leftBound, rightBound: leftChild.rightBound)
      let rightResult = rightChild.query(withLeftBound: rightChild.leftBound, rightBound: rightBound)
      return function(leftResult, rightResult)
    }
  }

同样，这是一种递归方法。它检查四种不同的可能性。

首先，我们检查查询段是否等于当前节点负责的段。如果是，我们只返回此节点的值。

equalSegments

查询段是否完全位于右子节点中？如果是这样，则递归地对右子节点执行查询。

rightSegment

查询段是否完全位于左子节点内？如果是这样，则递归地对左子节点执行查询。

leftSegment

如果不是上述任何一个，则意味着我们的查询部分存在于两个子节点中，因此我们将查询结果组合在两个子节点上。

mixedSegment

在playground 测试：

let array = [1, 2, 3, 4]

let sumSegmentTree = SegmentTree(array: array, function: +)

sumSegmentTree.query(withLeftBound: 0, rightBound: 3)  // 1 + 2 + 3 + 4 = 10
sumSegmentTree.query(withLeftBound: 1, rightBound: 2)  // 2 + 3 = 5
sumSegmentTree.query(withLeftBound: 0, rightBound: 0)  // just 1
sumSegmentTree.query(withLeftBound: 3, rightBound: 3)  // just 4

查询树需要O(log n)时间。

更换选项

线段树中节点的值取决于它下面的节点。因此，如果我们想要更改叶节点的值，我们也需要更新其所有父节点。

代码:

  public func replaceItem(at index: Int, withItem item: T) {
    if leftBound == rightBound {
      value = item
    } else if let leftChild = leftChild, rightChild = rightChild {
      if leftChild.rightBound >= index {
        leftChild.replaceItem(at: index, withItem: item)
      } else {
        rightChild.replaceItem(at: index, withItem: item)
      }
      value = function(leftChild.value, rightChild.value)
    }
  }

像往常一样，这适用于递归。如果节点是叶子，我们只需更改其值。如果节点不是叶子，那么我们递归调用 replaceItem(at: ) 来更新它的子节点。之后，我们重新计算节点自己的值，以便它再次更新。

更换项目需要O(log n)时间。

有关如何使用线段树的更多示例，请参阅 playground。

扩展阅读

懒惰传播的执行和说明。

线段树在PEGWiki的百科

作者：Artur Antonov
翻译：Andy Ron
校对：Andy Ron