5.5 线段树（一）

[giscus[bot]]

5.5 线段树（一）

1. 线段树简介 1.1 线段树的定义 线段树（Segment Tree）：一种基于分治思想的二叉树，用于在区间上进行信息统计。它的每一个节点都对应一个区间 [left, right] ，left、right 通常是整数。每一个叶子节点表示了一个单位区间（长度为 1），叶子节点对应区间上 left == right。每一个非叶子节点 [left, ...

https://algo.itcharge.cn/05_tree/05_05_segment_tree_01/

[ValiantCat]

3.2 部分 线段树的区间查询，为什么有个
self.__pushdown(index) 操作，感觉没用

[HalfCheesee]

在访问时，要看该节点的子节点是不是被标记了但还没修改

[HalfCheesee]

def __update_interval(self, q_left, q_right, val, index, left, right):
    
    if left >= q_left and right <= q_right:     # 节点所在区间被 [q_left, q_right] 所覆盖
        interval_size = (right - left + 1)      # 当前节点所在区间大小
        self.tree[index].val = interval_size * val # 当前节点所在区间每个元素值改为 val
        self.tree[index].lazy_tag = val         # 将当前节点的延迟标记为区间值
        return
    if right < q_left or left > q_right:        # 节点所在区间与 [q_left, q_right] 无关
        return 0

这端代码中
self.tree[index].val = interval_size * val # 当前节点所在区间每个元素值改为 val
是什么意思啊，为什么可以 当前节点所在区间每个元素值改为 val
在build 中 tree[index].val 存的是聚合值

[HalfCheesee]

def __update_interval(self, q_left, q_right, val, index, left, right):

if left >= q_left and right <= q_right:     # 节点所在区间被 [q_left, q_right] 所覆盖
    interval_size = (right - left + 1)      # 当前节点所在区间大小
    self.tree[index].val = interval_size * val # 当前节点所在区间每个元素值改为 val
    self.tree[index].lazy_tag = val         # 将当前节点的延迟标记为区间值
    return
if right < q_left or left > q_right:        # 节点所在区间与 [q_left, q_right] 无关
    return 0

这端代码中
self.tree[index].val = interval_size * val # 当前节点所在区间每个元素值改为 val
是什么意思啊，为什么可以 当前节点所在区间每个元素值改为 val
在build 中 tree[index].val 存的是聚合值

[haz053ucsd]

似乎动态开点的code有bug， 如果function取求和函数，先update [20, 28] 每个数加一，然后再去搜索[27, 29]的值，会得到0

[changdali1207]

请问大家有没有推荐看的视频关于线段树的，这章对新手不太友好。