第 3 章 · 03 数据结构学习路径串联

第 3 章 · 03 数据结构学习路径串联

本节定位:对应 OI Wiki docs/ds/ 全 59 篇的整体导读 + 学习路径。难度:进阶(串联)。前置依赖:本章 01-02 节。

⚠️ 注意:数据结构不是孤立学的,它们之间有强依赖。学线段树前不会二叉树和树状数组,等于盖楼没打地基。这一节帮你建立"全景图",看清 59 篇 Wiki 页面怎么串成一条学习路径。

知识地图

数据结构完整依赖图

把 docs/ds/ 的核心结构按学习依赖关系画出来:

读懂这张图:箭头表示"学后者需要先学前者"。可以看出线性结构 + 二叉树是所有进阶结构的共同地基;线段树和平衡树是两大分支,各自延伸出可持久化版本;最终汇合到第 7 章的 LCT(Link-Cut Tree)。

docs/ds/ 完整目录导读(59 篇)

按难度和主题分组:

基础线性(本节 01 已讲)
stack.md / queue.md / linked-list.md / monotonic-stack.md / monotonic-queue.md / hash.md

基础树形(本节 01 已讲)
bst.md / binary-heap.md / heap.md / dsu.md / dsu-complexity.md / sparse-table.md / fenwick.md

线段树家族(本节 02 已讲 + 进阶)

• seg.md:线段树基础(★ 必精)
• persistent-seg.md:可持久化线段树 / 主席树(省选级)
• seg-in-balanced.md / seg-in-bit.md / seg-in-seg.md:线段树嵌套(树套树)
• seg-beats.md:Segment Tree Beats(区间最值操作)
• seg-merge-split.md:线段树合并分裂
• divide-combine.md / divide-and-conquer-on-tree.md:相关

平衡树家族(本节 02 已讲 + 进阶)

• treap.md:Treap(★ 必精)
• splay.md:Splay(更通用但常数大,LCT 的基础)
• avl.md / sbt.md / rbtree.md / llrbt.md / aa-tree.md / wblt.md:AVL / SB树 / 红黑树 / 左偏红黑树 / AA树 / WBLT(了解即可,竞赛少用)
• cartesian-tree.md:笛卡尔树(Treap 的特例)
• skiplist.md:跳表

可持久化

• persistent.md:可持久化总览
• persistent-seg.md / persistent-trie.md / persistent-balanced.md / persistent-heap.md / persistent-block-array.md:各类可持久化结构

堆的高级变体

• leftist-tree.md:左偏树(可合并堆)
• pairing-heap.md:配对堆(实际很快)
• huffman-tree.md:Huffman 树
• kinetic-tournament-tree.md:动态树状竞赛树

分块类(第 7 章详讲)

• block-array.md / block-list.md:分块数组 / 分块链表
• decompose.md:分块总览
• bit-in-block-array.md:树状数组套分块

树的高级操作(第 7 章详讲)

• lct.md:Link-Cut Tree(动态树,★ 省选级)
• ett.md:Euler Tour Tree
• top-tree.md / hld.md:Top Tree / 树链剖分(树链剖分其实在 docs/graph/hld.md)
• kdt.md:KD 树(高维)
• li-chao-tree.md:李超线段树(线段维护线段)
• tree-decompose.md:树分块

其他

• cat-table.md:猫树
• finger-tree.md / pq-tree.md / sqrt-tree.md / global-bst.md / sgt.md / balanced-in-seg.md:少见结构

常见组合(高频考点)

数据结构题往往不是单用,而是组合:

1. 线段树 + 懒标记:区间加/乘/覆盖,最经典组合,P3372/P3373 系列。
2. 树状数组 + 逆序对:离散化后按位置倒序扫,query(a[i]) 求比 a[i] 小的已加入元素。或归并排序求逆序对。
3. 并查集 + Kruskal:最小生成树,把边按权排序,依次尝试加入,并查集判环(第 4 章)。
4. 线段树优化 DP:转移涉及区间最值/求和时,用线段树 O(\log n) 转移(第 5 章 DP 会用)。
5. 树套树:线段树套平衡树(二维数点)、树状数组套权值线段树(动态区间第 k 小),见 docs/ds/seg-in-balanced.md。
6. 主席树 + 区间第 k 小:docs/ds/persistent-seg.md 经典应用。
7. 线段树合并:多棵权值线段树合并,处理树上路径信息(docs/ds/seg-merge-split.md)。

学习建议

难度阶梯

按这个阶梯循序渐进,每阶吃透再进下一阶:

第一阶(入门进阶,CSP-S 水平)
栈/队列/链表 → 单调栈/单调队列 → 哈希 → 并查集 → ST 表 → 树状数组 → 二叉堆(priority_queue)。学完这一阶,CSP-S 数据结构题基本能做。

第二阶(进阶核心,NOIp 水平)
线段树(★ 懒标记)→ Treap/FHQ(★ 平衡树)。学完这一阶,NOIp 数据结构题不再怕。这是本章 02 节的内容。

第三阶(高阶,NOI 省选)
可持久化线段树(主席树)→ 树套树 → 线段树合并 → 李超树 → Splay → 笛卡尔树。这一阶是省选的入门门槛。

第四阶(省选/IOI,第 7 章)
LCT(动态树)→ Top Tree → 树分块 → KD 树。这一阶在本书第 7 章,本章不展开。

前置依赖提醒

• 平衡树 → 第 7 章 LCT:LCT 基于 Splay,所以学 LCT 前必须会 Splay(docs/ds/splay.md)。Splay 比 Treap 难一点,常数大但更通用(支持区间操作,LCT 必备)。
• 线段树 → 第 5 章 DP:线段树优化 DP 是 NOIp 常见套路,本章学好线段树,第 5 章才能用。
• 树状数组 → 第 4 章图论:逆序对、树状数组优化 DP 都会用到。

💡 学习提示:数据结构的"性价比"差异很大。并查集 20 行、树状数组 30 行、线段树 80 行、Treap 100 行、主席树 150 行、LCT 200 行。代码量翻倍但能解决的题目也翻倍,但学习时间也翻倍。前期先把高性价比的刷熟,后期再啃大招。

怎么用 Wiki 全目录

打开 docs/ds/index.md(数据结构总览页),Wiki 自己有分类导航。结合本节的全景图,你能快速定位"我想查 XXX 在哪页"。学新结构时,流程是:

1. 本地图(本节)建立它在全景中的位置。
2. 打开对应 Wiki 页面读定义、过程、代码、复杂度。
3. 找对应模板题刷 5-10 道。
4. 回本章 02 节如果是难点,看慢节奏精讲补增量。

本节要点

1. docs/ds/ 59 篇按依赖关系:线性 → 二叉树 → (线段树 / 平衡树) → 可持久化 → LCT。
2. 线性结构 + 二叉树是所有进阶结构的共同地基,务必先打牢。
3. 常见组合:线段树+懒标记 / 树状数组+逆序对 / 并查集+Kruskal / 线段树优化DP / 树套树 / 主席树。
4. 难度阶梯:第一阶(CSP-S:并查集/ST表/树状数组)→ 第二阶(NOIp:线段树/Treap)→ 第三阶(省选:主席树/树套树)→ 第四阶(LCT,第 7 章)。
5. 平衡树是第 7 章 LCT 的前置,线段树是第 5 章 DP 优化的前置,数据结构与后续章节强关联。