罗罗编程学习记录
本页内容 展开查看

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+ 树与数据库索引
  • [ ] 跳表与平衡树对比
  • [ ] 线段树合并