Bo2SS

[学习数据结构主要关注解决的是什么问题]

课程内容#

前置知识#

• 解决的问题是什么？区间的修改与查询 [针对积性函数——Wiki]
• 问题背景
  • 
  • 单点修改、区间查询（基础版）
    • Modify (ind, val)：修改 ind 位置的值为 val
    • Query (start, end)：查询 start~end 位置值的和
  • 区间修改、区间查询（进阶版）
  • 单点修改、单点查询（用不着线段树，数组即可）
  • 区间修改、单点查询（其实就是进阶版的特例）

基础版线段树#

• 区间组成的树→区间的和值组成的树 [线段树]
  • 
  • 👇
  • 
  • 【构建过程】采用的分治的思想，将总区间分成左右两部分，一直进行下去，直到区间中只剩下一个结点为止
  • 【要维护的性质】结点统计的是一个区间的和值
    • 叶子结点代表了原序列中的单个位置的值
  • [PS] 回顾：树的结点代表集合，边代表关系
• 单点修改
  • 递归，找到要修改的结点，修改，然后
  • 回溯，修改路径上每一个祖先结点的统计和值 [根结点到叶结点的路径]
• 区间查询
  • 一个点可能代表一个区间的和值，查询更快
    • 如果直接使用数组，则需要一个一个查值
    • 如果借助前缀和数组，则单点修改非常耗时
• ⭐线段树，其实是用来维护一维序列的高级数据结构
  • 时间复杂度 [与树高有关]
    • 单点修改：O (logN)
    • 区间查询：O (logN)
    • N 代表一维序列的长度
• ❓ 问题思考
  • 若采用完全二叉树的存储方式，N 个点的线段树最多需要多少个结点空间？【4N】
    • 先考虑用普通二叉树 [线段树一定是满二叉树] 存储，参考上图
    • 叶子结点数为 N，则度为 2 的结点数为 N - 1 [二叉树的性质：度为 0 的结点比度为 2 的结点多 1 个]，所以结点数为 2N - 1
    • 而如果用完全二叉树的存储方式，则最多还要预留 2 倍叶子结点数的结点空间 2N [完全二叉树的性质：两个子结点的索引与父结点 i 之间的关系是 2i 和 2i + 1 ]
    • 所以最多需要 4N 个结点空间
  • 如何做区间修改？ [大小为 m 的区间上每一个值都做修改]
    • 基于线段树的基本操作：O (m * logN)，相当于脱了裤子放屁
    • 而直接在原有区间上修改：O (m)，本身就比用线段树好
    • 请看进阶版：O (logN)
• [PS] 只适用于单点修改、区间查询 【基础版】
  • 当面对区间修改的时候，基础版的线段树效率上还不如直接在一维序列上修改

进阶版线段树#

区间修改 [⭐]#

• Modify 操作
  • 
  • ⭐懒标记：不对其子结点立即发数值，碰到结点查询 [修改操作/ 查询操作遍历时] 时才下发
  • 类比 [懒政]：皇帝 [根结点] 给百姓 [叶子结点] 下发粮食，先发给上级 [子结点]，上级会先收着，等到皇帝亲自视察时才往下分发粮食
• Query 操作
  • 
  • 触发懒标记下发数值
• 时间复杂度 [同区间查询操作]：O (logN)

关键词#

• 完全二叉树 [存储结构]
• 区间 [每个结点的维护范围]
• 向上更新 [回溯过程]
• 下沉标记 [懒标记]
• ⭐口诀⭐ 下沉发生在递归之前，向上发生在递归之后
  • 标记下沉发生在递归之前，向上更新发生在具有修改操作的递归之后

随堂练习#

HZOJ-222：线段树模板 (一)#

样例输入

6 5
6 9 4 3 2 1
2 2 5
1 2 3
2 1 6
1 5 12
2 1 6

样例输出

9
6
12

• 思路
  • 父结点所在区间的最大值可以由子结点得到
  • 【线段树应用场景】父结点的相关信息可以由子结点得到
• 代码
• ① 易理解版 [有 l、r]
  • 
  • 
  • 
  • 使用 scanf/printf 读入数据或者关闭同步流，否则会超时
  • 查询最大值操作，在缩小查询范围时始终保持修改查询区间边界，否则会有扩大查询区间的可能
• ② 优化版 [无 l、r]
  • 
  • 
  • 
  • 可做空间的优化：结点不存储 l、r 信息
    • 不影响建树过程
    • ⭐修改和查询操作额外添加【当前结点所维护的区间范围】

HZOJ-223：线段树模板 (二)#

样例输入

6 5
6 9 4 3 2 1
2 2 5
1 2 3 5
2 1 6
1 5 12 3
2 1 6

样例输出

18
35
41

• 思路
  • 加入懒标记
  • 注意输出的提示：答案在 long long 范围内
• 代码
  • 
  • 
  • 
  • 一定要区分好【结点维护的区间范围 l ~ r】，以及【查询的区间 x ~ y】
  • [PS] 学会利用 flag 起到注释调试代码的效果；数据范围为 long long
  • ⭐⭐⭐只要遍历就需要下沉，即使是区间修改时
    • 如果区间修改中遍历结点时【不下沉标记】，向上更新可能引发问题
    • 可以尝试测试两种方式下，下面输入的输出
      • ❗ 连续两次区间修改，第二次修改层数更深，向上更新时会少考虑懒标记，因为向上更新和值的操作只会看子树的和值，默认自己没有懒标记了
      • 遍历时就下沉标记实现更简单，也更易理解

5 5
1 2 3 4 5
1 1 3 2
1 1 2 2
2 1 3

• 结果如下：
  • 
  • modify (1, 3, 2) : 1, 1, 5, 15，代表给 [1, 3] 区间 + 2，此时在 1 号结点 [根结点]，维护区间为 [1, 5]，sum 为 15
  • 自行画树形图可加深理解

思考点#

• 好好琢磨下沉标记和向上更新的过程！

Tips#

• 关注口诀，船长归纳得很妙！
• 更多习题可跳转：《面试笔试算法下》——6 树状数组、线段树练习题