OI Wiki 学习地图 · 第 3 章 进阶路径一:数据结构

OI Wiki 学习地图 · 第 3 章 进阶路径一:数据结构

章节摘要:本章进入进阶,讲数据结构(docs/ds/ 59篇)。从线性结构(栈/队列/链表)到树形结构(二叉树/堆/并查集),再到进阶的线段树/Treap/平衡树。线段树 docs/ds/seg.md 和 Treap docs/ds/treap.md 是本章难点(★),做慢节奏精讲(懒标记下传/平衡树旋转)。本章共 3 节,前置依赖为第 1-2 章。

路径坐标

进阶(本章) → 省选(LCT 第7章)

学习目标

1. 掌握线性与树形基础数据结构。
2. 理解线段树与懒标记(★)。
3. 理解 Treap/平衡树(★)。
4. 建立数据结构学习路径。

子章节导航

01 线性与树形基础(对应 docs/ds/)

栈/队列/链表/哈希表;二叉树/二叉搜索树/堆;并查集(路径压缩/按秩合并);ST表;树状数组;引用 docs/ds/ 基础页。

02 线段树与Treap难点精讲 ★

线段树 docs/ds/seg.md(区间操作/懒标记lazy propagation下传/动态开点/可持久化);Treap docs/ds/treap.md(树堆/旋转/分裂合并/随机优先级平衡);Splay;AVL;红黑树;为什么需要平衡树;慢节奏精讲懒标记与旋转。

03 数据结构学习路径串联

从基础到进阶的依赖关系;先学什么后学什么;常见组合(线段树+懒标记/树状数组+逆序对/并查集+Kruskal);docs/ds/ 完整目录导读。

前置知识与后续延伸

前置:第1-2章。后续:第4章图论(并查集用于MST);第7章LCT。