[L3] 11_树形结构

11_树形结构

核心哲学：将线性数组转化为对数层级的树形结构，核心在于“信息合并”。
所有的树形结构本质上都是在处理区间信息的动态化。

1. 知识图谱与演化

• 核心工具: 树状数组（BIT），线段树（Segment Tree），平衡树（BST），ST 表（Sparse Table）。

• 演化路径:

  1. 静态前缀和：查询 $O(1)$，修改 $O(N)$，无法应对动态修改。

  2. ST 表: 基于倍增思想，通过预处理实现 $O(1)$ 查询，前提是信息满足幂等性。

  3. 树状数组：通过二进制分解，实现 $O(\log{N})$ 维护可差分信息。

  4. 线段树：递归划分区间并合并满足结合律的摘要，区间修改再由懒标记等机制扩展。

2. 决策矩阵

• 场景 A: 只涉及单点修改与前缀类（和、异或）统计，要求低时间复杂度。

  • 决策：树状数组

• 场景 B: 涉及复杂的区间修改（乘加、覆盖），以及非差分信息（最值、平方和）。

  • 决策：线段树基础理论

3. 核心板块索引

3.1 基础模型

• 树状数组: 轻量的二进制前缀和。

• 倍增策略: 静态 RMQ 的对数级预处理，常数查询。

• 线段树基础理论：固定坐标下的递归划分、区间摘要与基础查询。

• 线段树信息合并：跨边界答案、有限状态与方向性摘要。

• 浅谈线段树懒标记：区间操作怎样作用于摘要，以及多个待执行操作怎样复合。

3.2 进阶变体

• [[势能线段树]]: 针对取模、开方等特定修改的“暴力剪枝”。

• [[主席树]]: 时空复用，解决历史版本查询。

4. 依赖与规划

1. 基础: 盲打 BIT，熟练掌握 ST 表的预处理。

2. 提升: 攻克线段树 Lazy Tag 逻辑。

3. 进阶: 掌握线段树合并与李超树。