内容简介:线段树算法是一种快速查询一段区间内的信息的算法, 由于其实现简单, 所以广泛应用于程序设计竞赛中。线段树是一棵完美二叉树, 即所有的叶子节点的深度均相同, 并且所有的非叶子节点都有两个子节点。每个节点维护一个区间, 这个区间为父节点二分后的子区间, 根节点维护整个区间, 叶子节点维护单个元素, 当元素个数为线段树可以提供不同的功能, 例如最常见的求区间内的最大最小值和求区间内的和, 还有其他类似的功能, 实现思路基本相同
线段树算法是一种快速查询一段区间内的信息的算法, 由于其实现简单, 所以广泛应用于程序设计竞赛中。
线段树是一棵完美二叉树, 即所有的叶子节点的深度均相同, 并且所有的非叶子节点都有两个子节点。每个节点维护一个区间, 这个区间为父节点二分后的子区间, 根节点维护整个区间, 叶子节点维护单个元素, 当元素个数为 n
时, 对区间的操作都可以在 O(log n)
的时间内完成, 因为此时树的深度为 log2 n + 1
, 每次操作只需从叶子节点开始, 往上更新至根节点, 每层只需更新相关的一个区间即可, 操作次数 log2 n + 1
, 即在 O(log n)
的时间内可完成。
可实现的功能
线段树可以提供不同的功能, 例如最常见的求区间内的最大最小值和求区间内的和, 还有其他类似的功能, 实现思路基本相同
求区间最小值(最小值)
给定任意数列 [a0, a1,...,an-1]
, 在 O(log n)
的时间内完成下列的两种操作
-
query(s, t)
求[as,as+1,...,at-1]
内的最小值(最小值) -
update(i, x)
把ai
的值改为x
求区间的和
给定初始值全为 0
的数列 [a0, a1,...,an-1]
, 在 O(log n)
的时间内完成下列的两种操作
-
query(s, t)
求[as,as+1,...,at-1]
内的和 -
add(i, x)
执行ai += x
代码实现
这里我们以 求区间最小值
内的最小值为例, 用 Python
来实现原始的一棵线段树
初始化
这里创建一个数组 dat[]
并赋予初始最大值, 为了让其成为一棵完美的二叉树, 便于计算, 我们把 n
扩大到 2的幂
, 由于我们在数组中填充了 int32
的最大整数 2147483647
, 所以多余出来的的元素总是最大值, 不会影响原来区间的结果
def init(self, n): self.INT_MAX = 2147483647 self.n = 1 while self.n < n: self.n *= 2 self.dat = [self.INT_MAX for i in range(2 * self.n - 1)]
更新元素
我们把一棵完美二叉树压成一个数组, 下标为 i
的子节点为 i*2+1 和 i*2+2
, a0
为根节点, 每次更新时, 首先更新叶子节点, 之后一层层往上更新, 节点 a[k] = min(a[k * 2 + 1],a[k * 2 + 2])
, 操作在 O(log n)
的时间内完成
def update(self, k, a): k += self.n - 1 self.dat[k] = a while k > 0: k = (k - 1) // 2 self.dat[k] = min(self.dat[k * 2 + 1],self.dat[k * 2 + 2])
查询元素
query
的功能为查询 [a, b)
区间内的最小值, 参数 k, l, r
是辅助参数
- k 当前计算的节点
- l, r 当前节点区间的范围
[a,b)
, 不在 k
节点管理的区间 [l, r)
内时, 直接返回 INT_MAX
当 [a,b)
, 重合于 k
节点管理的区间 [l, r)
时, 直接返回 k
节点的值
否则, 递归 k
的两个子节点, 返回其中的最小值
def query(self, a, b, k, l, r): if r <= a or b <= l: return self.INT_MAX if a <= l and r <= b: return self.dat[k] else: vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2) vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r) return min(vl, vr)
结尾
至此我们就简单地实现了一棵线段树, 这只是线段树的其中一种形式, 线段树还有其他的变体。线段树的使用实例可以看我的另一篇文章 https://laboo.top/2018/11/02/acm-lc-45/#more
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and
George F. Luger、William A Stubblefield / Addison Wesley / 2008-09-04 / USD 22.20
This book is designed for three primary purposes. The first is as a programming language component of a general class in Artificial Intelligence. From this viewpoint, the authors see as essential that......一起来看看 《AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and 》 这本书的介绍吧!