图解线段树(segment tree)

图解线段树(segment tree)
今日咱们学习一下线段树。首要需求阐明一下线段树呈现的布景。有些「区间问题」运用线段树这种数据结构,能够使得算法的时刻复杂度从 O( n ) 降低到 O(log n),可是它会需求额定的存储空间,算法不便是用空间交换时刻的吗?举个比方,在某 App 的数据中,求 18 年 消费最高、最低的用户、1 到 6 月的销售额,这些相似的问题,能够运用线段树来求解。假如有 10 条数据,分别为 「8,10,20,7,40,32,12,3,19,26」表明 1 到 9 月份每月的销售额。求 1-4 月的销售额和是多少。能够遍历数组直接求和即可,可是咱们有更高效的办法。咱们画一颗线段树,赤色存储的值是下标对应的和,当然赤色部分还能够表明其它事务数据,比方最大值,最小值:求 1-4 月的和,在数组中对应的下标为 0-3,模仿一下查找进程:从根节点开端,0-3 在左子树,查到 85 这个节点;0-3 区间既在 85 的左子树,又在其右子树,0-2 区间的和为 38;85 的右子树为 47,因为已求出 0-2 的和,只需求得 3 这个下标对应的值即可,为 7(47的左子树);0-2 区间的和为 38,下标 3 对应的值为 7,核算的成果为 45。整个求解进程,不需求太多的遍历,时刻复杂度为 O(logn)。赤色的部分,不只能够表明区间的和,也能够表明最大、最小值,或许其它的事务,全部因需求而异。线段树的效果其实便是处理一些「区间问题」,经过运用额定的空间来记载某个区间的值,经过「平衡二叉树」存储对应的数据,使得查询时刻复杂度降低到 O(logn)。线段树能够运用数组来完成,你还记得堆的完成吗?它便是经过数组来完成的着手写个“堆”。

标签:,

发表评论

电子邮件地址不会被公开。 必填项已用*标注