线段树?? -> 区间操作利器

• 先回想一下下有几种数据结构可以操作区间的信息

那么线段树就是可以在O(logN)时间内实现这些操作的数据结构, 主要运用了分治算法

基本结构与建树

• 过程：
• 线段树将每个长度不为1的区间划分成左右两个区间进行递归求解，把整个线段划分成为一个类似二叉搜索树的结构，通过合并左右两区间信息来求的该区间的信息

• 假设总的区间为 [s, t]

• 左儿子节点区间 => [s, (t + s) >> 1]

• 右儿子节点区间 => [(s + t) << 1 | 1, t]

• 实现过程
• 通过递归建树。假设当前根节点为p，如果根节的管理区域的区间长度已经是1，则直接通过原始数组的值初始化该节点。否则将该区间从中间分成两个子区间
• 进入左右子节点进行建树，最后合并两个子节点的信息

• ！！！注意在线段树中所有操作下标都从1开始！！！

• 图⬇️

线段树的区间更新 & lazy标记!

• lazy标记的产生:
• 如果我们对线段树进行区间更新的时候每次都要遍历其涉及的所有区间, 那么复杂度和不用线段树没啥区别
• 所有就引入了 lazy标记 数组来简化更新操作

• lazy标记:
• 简单来说就是延迟了对节点信息的更新，从而减少了不必要的操作次数，通过打标机的方法表明该节点对应的区间在某一次操作中被更改，但是先不更新该节点的子节点信息，实质性的修改则在下一次访问带有标记的节点时才lazy标记的下放（对子节点的更新）

• 具体操作过程:
1. 创建一个 lazy = [0] * (4 * n) => 用于存储对应线段树节点的更新标志
2. 每次执行的时候通过递归找到与这个区间有交集的区间并且打上标记，但是先不更新这些子节点的信息，下一次访问带标记的节点是才进行下放

📎 参考文章

• 无