数据结构¶
按「线性结构 → 哈希与堆 → 区间数据结构」的顺序学习。
本部分 15 章，配套 91 道真题。点章号进入正文。
区间数据结构怎么选¶
fenwick / segment-tree / block / sparse-table 四章讲的是同一个问题的四种答案，
放在任何一章里都会让另外三章缺一块，所以这张表放在目录页。
| 结构 | 预处理 | 查询 | 修改 | 空间 |
|---|---|---|---|---|
| ST 表 | \(O(n\log n)\) | \(O(1)\) | ❌ | \(O(n\log n)\) |
| 线段树 | \(O(n)\) | \(O(\log n)\) | ✅ | \(O(n)\) |
| 树状数组 | \(O(n)\) | \(O(\log n)\) | ✅（最值只能前缀） | \(O(n)\) |
拿到一道区间题，按这张表从上往下走，第一个匹配的就是答案。
| 条件 | 选择 |
|---|---|
| 无修改、只查区间和 | 前缀和 |
| 无修改、只查区间最值 | ST 表 |
| 所有修改在所有查询之前 | 差分数组 |
| 单点改 + 区间和 | 树状数组 |
| 区间改 + 单点查 | 树状数组（差分） |
| 区间改 + 区间和 | 双树状数组 |
| 求逆序对 / 动态第 \(k\) 小 | 树状数组 + 倍增 |
| 区间改 + 区间最值 | 线段树（懒标记） |
| 区间赋值、区间乘、多重标记 | 线段树 |
| 操作很怪（开根、小于计数、位运算） | 分块 |
| \(n, q \ge 5\times10^5\) 且要区间改区间查 | 双树状数组，并做好卡常准备 |
| 能离线 | 先考虑离线：排序 + 树状数组往往能降一个数量级 |