算法基础篇(6)------线段树

    xiaoxiao2021-03-25  48

    ● 每周一言

    计划,贵在坚持。

    导语

    线段树顾名思义,节点由线段(通常指数组中的一段子数组,点可以看成线段的特殊形式)组成,主要用于高效解决连续区间的动态查询问题,比如求序列任意区间内的最大最小值。那么,线段树到底有何优势?又是如何实现的?

    线段树

    这次简单粗暴一点,我们直接上例子,采取一目了然法来理解线段树的算法思想。不妨就举求解区间最大值的例子:一个长度为N的序列,每次询问任意一段区间的最大值是多少。

    一开始容易想到,可以通过每次遍历这段区间的序列来找出最大值,算法时间复杂度为O(kN)。但是当序列长度很长的情况下,O(N)实在太慢。而线段树由于具有二叉结构,可以将该问题降至O(klogN)的时间复杂度。比如一个长度为6的序列[3, 2, 6, 5, 1, 9],构造线段树如下图所示:

    采用递归建树。绿色表示叶子结点,表示原序列,用数组存储;蓝色表示非叶子节点,表示该线段区间的最大值,可以用链表存储。每次询问某段区间的最大值时,从根节点开始匹配,线段若分处于左右节点,则分裂继续匹配,直到线段匹配成功然后回溯比较最大值即可,每次查询的时间复杂度为O(logN)。

    延迟标记 上面只说了线段树的基本特质,而延迟标记则是线段树的精华所在。当原序列中某一段区间的值发生了变化时,比如同时增加d,O(N)暴力枚举法的逻辑甚至会变得十分复杂。而线段树只需要O(logN)的时间复杂度更新树即可,方法便是给每个节点均增加一个延迟标记,这个标记的初始值均为0。

    比如在[0 - 2]区间内的数均增加4。从根节点出发开始匹配,发现根节点线段[0 - 5]包含[0 - 2],往子节点继续查询,发现左节点线段包含[0 - 2],则将其延迟标记值增加4,且最大值加4变为10。由于[0 - 2]线段已全部被包含,因此不再往下查询,开始回溯,将根节点的值更新为新子节点之间的最大值10。更新后的线段树如下图所示:

    上图中三角形内的数字代表每个节点的延迟标记值。之后的每次最大值查询,如果当前节点的延迟标记大于0,则向下查询时,带走延迟标记,重复上述延迟操作直到完全匹配。这种“延迟查询”的方式大大加速了序列的更新与查找效率。比如接下来再查询[0 - 1]的最大值,更新后的线段树如下图所示: 可知新的[0 - 1]之间最大值为7。这里需要注意一点,如果带走延迟标记,为了保持左右子节点的正确,需至少往每个子节点带一次。敬请期待下节内容 树状数组。

    结语

    感谢各位的耐心阅读,后续文章于每周日奉上,欢迎大家关注小斗公众号 对半独白!

    转载请注明原文地址: https://ju.6miu.com/read-33926.html

    最新回复(0)