[L2] 10_数据结构

核心哲学：数据结构是通过高效数据管理来优化时间复杂度。
要么把数据切成块处理（分治/块），
要么把重叠的信息存起来复用（持久化/动态树）。

1. 知识图谱与演化

• 核心模型: 递归分治、路径压缩、时空复用、根号平衡。

• 演化路径:

  1. 基础线性：栈、队列。解决端点或全局问题。

  2. 树形化：树状数组、线段树。利用对数层级结构解决线性扫描。

  3. 动态化/持久化：主席树、LCT。利用历史版本或维护动态拓扑。

  4. 根号平衡：莫队、分块。通过“暴力分组”解决非结合律信息维护。

2. 决策矩阵

• 信息可差分（和/异或）+ 单点修改：树状数组。

• 相邻区间摘要满足结合律 + 动态维护：线段树基础理论；若还有区间修改，再用 浅谈线段树懒标记 判断操作能否整体作用与复合。

• 查询历史版本 / 区间第 K 大：[[Note] 主席树]。

• 动态连通性 / 传递性逻辑：并查集理论。

• 动态断边/连边 / 树上路径信息：[[Note] LCT]。

• 无结合律 / 离线区间查询：[[Note] 莫队体系] 或 [[Note] 分块体系]。

• 静态区间答案可写成 $\sum_x F(cnt_x)$：先用 [[区间频次统计模型]] 判断走莫队增删，还是固定端点后把阈值贡献位置化。

• 多维限制中有一维可离线排序：用 [[扫描线模型]] 消去这一维，再维护动态截面。

• 信息满足幂等性（Max/Min/GCD）+ 静态海量查询：采用 倍增策略。

3. 核心板块索引

3.1 [L3] 11_树形结构

• 树状数组: 轻量的前缀和维护。

• 线段树基础理论：由递归划分、区间摘要与节点不变量构成的动态区间维护骨架。

• 线段树信息合并：从父区间需求反推边界接口、有限状态与有序转移。

• 浅谈线段树懒标记：从整段操作出发，推导 Info 的整体更新与 Tag 的有序复合。

• [[Note] 线段树合并]：树上信息的合并

• [[Note] 主席树]：可持久化线段树，跨越时间轴的查询。

• [[Note] 平衡树]：Splay 与 FHQ-Treap 的动态排序。

• [[Note] 笛卡尔树]：结合堆与BST性质的结构。

3.2 [L3] [[12_连通性结构]]

• 并查集理论：集合合并与动态连通。

• [[Note] LCT]：(Link-Cut Tree) 动态树问题。

• [[Note] 可撤销并查集]: 撤销与历史版本。

3.3 [L3] [[13_分块与莫队]]

• [[Note] 分块体系]: 根号平衡的艺术。

• [[Note] 莫队体系]: 基于离线排序的区间移动。

3.4 跨结构的问题模型

• [[区间频次统计模型]]：从按权值贡献出发，统一莫队增删与固定端点的位置贡献。

• [[扫描线模型]]：排序消去一个维度，根据答案维护点数、覆盖长度或截面最值。

4. 近期推荐

• P5677 配对统计：先把值域最近邻还原成有限候选边，再离线转成区间内二维数点；
• P1631 序列合并：把二维和表拆成多条有序序列，用小根堆维护各路当前首项；
• CF19D Points：线段树先定位第一个可行横坐标，再由列内有序集合定位最小纵坐标。