02.11 高级数据结构
所属:全栈开发面试题库 / 02 数据结构与算法
覆盖范围
- 线段树与树状数组
- 稀疏表与单调队列栈进阶
- 平衡树家族(AVL/红黑树/Treap/Splay)
- 可持久化与并查集进阶
子主题
| 编号 | 主题 | 覆盖范围 |
|---|---|---|
| 02.11.1 | 线段树与树状数组 | 区间查询/区间更新、懒标记、二维、动态开点 |
| 02.11.2 | 稀疏表与单调队列栈进阶 | ST 表 RMQ、单调队列滑动窗口、单调栈柱状图/接雨水 |
| 02.11.3 | 平衡树家族 | AVL/红黑树/Treap/Splay、旋转与适用场景 |
| 02.11.4 | 可持久化与并查集进阶 | 带权并查集、可撤销并查集、主席树、可持久化 |
面试题索引
| 编号 | 题目 | 难度 | 状态 | 备注 |
|---|---|---|---|---|
| 02.11.1-001 | 线段树区间求和点修改 | 基础 | 已完成 | |
| 02.11.1-002 | 线段树区间更新懒标记 | 高级 | 已完成 | |
| 02.11.1-003 | 树状数组区间查询 | 基础 | 已完成 | |
| 02.11.1-004 | 树状数组区间修改区间查询 | 进阶 | 已完成 | |
| 02.11.1-005 | 线段树 vs 树状数组对比 | 基础 | 已完成 | |
| 02.11.1-006 | 懒标记下推顺序 | 高级 | 已完成 | |
| 02.11.1-007 | 线段树动态开点 | 进阶 | 已完成 | |
| 02.11.1-008 | 二维树状数组 | 进阶 | 已完成 | |
| 02.11.2-001 | ST 表稀疏表构建 | 进阶 | 已完成 | |
| 02.11.2-002 | ST 表 RMQ 查询 | 进阶 | 已完成 | |
| 02.11.2-003 | ST 表 vs 线段树 | 基础 | 已完成 | |
| 02.11.2-004 | 单调队列滑动窗口最大值 | 基础 | 已完成 | |
| 02.11.2-005 | 单调栈每日温度 | 基础 | 已完成 | |
| 02.11.2-006 | 单调栈柱状图最大矩形 | 进阶 | 已完成 | |
| 02.11.2-007 | 单调栈接雨水 | 进阶 | 已完成 | |
| 02.11.2-008 | 三者对比与适用场景 | 基础 | 已完成 | |
| 02.11.3-001 | AVL 树四种旋转 | 进阶 | 已完成 | |
| 02.11.3-002 | 红黑树五条性质 | 基础 | 已完成 | |
| 02.11.3-003 | 红黑树插入调整 | 高级 | 已完成 | |
| 02.11.3-004 | Treap 随机堆原理 | 进阶 | 已完成 | |
| 02.11.3-005 | Splay 伸展树原理 | 高级 | 已完成 | |
| 02.11.3-006 | 旋转操作本质 | 基础 | 已完成 | |
| 02.11.3-007 | 各平衡树适用场景 | 基础 | 已完成 | |
| 02.11.3-008 | BST 退化与平衡动机 | 基础 | 已完成 | |
| 02.11.4-001 | 并查集路径压缩与按秩合并 | 基础 | 已完成 | |
| 02.11.4-002 | 带权并查集 | 进阶 | 已完成 | |
| 02.11.4-003 | 可撤销并查集 | 高级 | 已完成 | |
| 02.11.4-004 | 可持久化线段树(主席树) | 高级 | 已完成 | |
| 02.11.4-005 | 主席树求区间第 K 大 | 高级 | 已完成 | |
| 02.11.4-006 | 可持久化 vs 可撤销 | 基础 | 已完成 | |
| 02.11.4-007 | 离线并查集 | 进阶 | 已完成 | |
| 02.11.4-008 | 可持久化数组 | 进阶 | 已完成 |
待整理清单
- [ ] B 树/B+ 树与数据库索引
- [ ] 跳表与平衡树对比
- [ ] 线段树合并