Fork me on GitHub

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

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.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。 例如,函数可以是求和,乘法,最小,最大,最大公约数等。

你的任务是:

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

例如,如果我们有一个数字数组:

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

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

101 + 14 + 29 + 5 + 61 = 210

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

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

1
2
3
4
5
6
7
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类的一个实例:

1
2
3
4
5
6
7
8
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>?
}

每个节点都有以下数据:

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

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

structure

每个节点的leftBoundrightBound标记为红色。

构建线段树

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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],它构建整个树,从根节点到所有子节点。

  1. 如果leftBoundrightBound相等,则递归终止。这样的SegmentTree实例表示叶节点。对于输入数组[1,2,3,4],这个过程将创建四个这样的叶节点:1234。我们只用数组中的数字填充value属性。

  2. 但是,如果rightBound仍然大于leftBound,我们创建两个子节点。我们将当前段划分为两个相等的段(至少,如果长度是偶数;如果它是奇数,则一个段将略大)。

  3. 递归地为这两个段构建子节点。 左子节点覆盖区间[leftBound, middle],右子节点覆盖[middle + 1, rightBound]

  4. 在构造了我们的子节点之后,我们可以计算自己的值,因为f(leftBound, rightBound) = f(f(leftBound, middle), f(middle+1, rightBound))。 这是数学!

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

获得查询结果

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)
}
}

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

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

equalSegments

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

rightSegment

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

leftSegment

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

mixedSegment

在playground 测试:

1
2
3
4
5
6
7
8
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)时间。

更换选项

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
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

坚持原创技术分享,您的支持将鼓励我继续创作!
0%