快速区间查询算法 - 线段树

psychola 发布于2019-07-30 18:34 / 2188人阅读

摘要：原博地址简介线段树算法是一种快速查询一段区间内的信息的算法由于其实现简单所以广泛应用于程序设计竞赛中。线段树是一棵完美二叉树即所有的叶子节点的深度均相同并且所有的非叶子节点都有两个子节点。

原博地址https://laboo.top/2018/11/24/xds/#more

简介

线段树算法是一种快速查询一段区间内的信息的算法, 由于其实现简单, 所以广泛应用于程序设计竞赛中。
线段树是一棵完美二叉树, 即所有的叶子节点的深度均相同, 并且所有的非叶子节点都有两个子节点。每个节点维护一个区间, 这个区间为父节点二分后的子区间, 根节点维护整个区间, 叶子节点维护单个元素, 当元素个数为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

欢迎关注我的博客公众号

私有云 GPU服务器线段树线段树 c++ 最小生成树算法二叉树算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/42656.html

面试算法实践与国外大厂习题指南

摘要：面试算法实践与国外大厂习题指南翻译自维护的仓库，包含了在线练习算法概述与大厂习题实战等内容。面试算法实践与国外大厂习题指南在线练习在线面试编程数据结构链表即是由节点组成的线性集合，每个节点可以利用指针指向其他节点。面试算法实践与国外大厂习题指南翻译自 Kevin Naughton Jr. 维护的仓库 interviews，包含了在线练习、算法概述与大厂习题实战等内容。笔者发现正好和...

genedna 2019-08-14 17:46 评论0 收藏0
我理解的数据结构（八）—— 线段树（SegmentTree）

摘要：示例解题代码注意，如果要在上提交解答，必须把接口和类的代码一并提交，这里并没有在写类中我理解的数据结构（八）—— 线段树（SegmentTree）一、什么是线段树 1.最经典的线段树问题：区间染色有一面墙，长度为n，每次选择一段墙进行染色，m次操作后，我们可以看见多少种颜色？m次操作后，我们可以在[i, j]区间内看见多少种颜色？showImg(https://segmentfau...

waltr 2019-08-16 13:36 评论0 收藏0
我理解的数据结构（八）—— 线段树（SegmentTree）

摘要：示例解题代码注意，如果要在上提交解答，必须把接口和类的代码一并提交，这里并没有在写类中我理解的数据结构（八）—— 线段树（SegmentTree）一、什么是线段树 1.最经典的线段树问题：区间染色有一面墙，长度为n，每次选择一段墙进行染色，m次操作后，我们可以看见多少种颜色？m次操作后，我们可以在[i, j]区间内看见多少种颜色？showImg(https://segmentfau...

shaonbean 2019-07-01 10:54 评论0 收藏0
LuxTdmZtIC

摘要：转载史上最简单的平衡树无旋作者博客地址使用此文件时请保留上述信息谢谢合作觉得文章不错请点击链接为博客点赞高能预警所有示例代码都是数组版的欢迎前置知识线段树请确保你完全理解最基础的线段树和区间加法和区间求和一简介无旋又称是范浩强大佬发明的一种【转载】史上最简单的平衡树——无旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

CoffeX 2019-08-02 15:24 评论0 收藏0
LuxTdmZtIC

摘要：转载史上最简单的平衡树无旋作者博客地址使用此文件时请保留上述信息谢谢合作觉得文章不错请点击链接为博客点赞高能预警所有示例代码都是数组版的欢迎前置知识线段树请确保你完全理解最基础的线段树和区间加法和区间求和一简介无旋又称是范浩强大佬发明的一种【转载】史上最简单的平衡树——无旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

tuantuan 2019-08-23 18:22 评论0 收藏0