第 3 章 · 01 线性与树形基础(对应 docs/ds/)

第 3 章 · 01 线性与树形基础(对应 docs/ds/)

本节定位:对应 OI Wiki docs/ds/(数据结构,59 篇)。难度:进阶。前置依赖:第 2 章(C++ STL + 复杂度)。

⚠️ 注意:数据结构是竞赛的"工具箱"。这一节列出的每个结构都有用,但性价比不同——并查集和树状数组投入产出比最高,线段树/平衡树是大招但门槛高。先吃透高性价比的,再啃大招。

知识地图

docs/ds/ 页面地图(基础部分)

OI Wiki 的 docs/ds/ 目录有 59 篇,从线性到树形到高级。本节先讲基础部分(线性结构 + 树形基础 + 并查集 + ST 表 + 树状数组),进阶的线段树/平衡树放第 02 节难点精讲。

线性结构

• docs/ds/stack.md:栈(LIFO,后进先出)。括号匹配、表达式求值、DFS 非递归用。
• docs/ds/queue.md:队列(FIFO,先进先出)。BFS 必备。
• docs/ds/linked-list.md:链表。竞赛中常用数组模拟链表(指针链表常数大)。
• docs/ds/monotonic-stack.md:单调栈。O(n) 求每个元素左右第一个比它大/小的位置。
• docs/ds/monotonic-queue.md:单调队列。滑动窗口最值 O(n),优化 DP 常用。

哈希

• docs/ds/hash.md:哈希表。哈希函数、冲突处理(链地址法 / 开放寻址法)。离散化是它的简化版。

树形基础

• docs/ds/bst.md:二叉搜索树 BST。中序遍历有序,是平衡树的基础概念。
• docs/ds/binary-heap.md:二叉堆。priority_queue 的底层。
• docs/ds/heap.md:堆总览(配对堆/左偏树/二项堆/斐波那契堆,见 docs/ds/pairing-heap.md / docs/ds/leftist-tree.md)。

高频必会

• docs/ds/dsu.md:并查集(Disjoint Set Union)。路径压缩 + 按秩合并,近乎 O(1)。
• docs/ds/sparse-table.md:ST 表(稀疏表)。O(n log n) 预处理,O(1) 区间最值(RMQ),不可修改。
• docs/ds/fenwick.md:树状数组(BIT / Fenwick Tree)。前缀和 + 单点修改,O(log n)。

并查集(极高频)

docs/ds/dsu.md。并查集维护"集合的合并与查询",核心两招:

1. 路径压缩:find 时把路径上所有点直接挂到根,后续查询近乎 O(1)。
2. 按秩合并:把小树合并到大树下,避免树退化成链。

int fa[N];
int find(int x){ return fa[x]==x ? x : fa[x]=find(fa[x]); }  // 路径压缩
void unite(int x,int y){ fa[find(x)] = find(y); }            // 朴素合并
​

只写路径压缩(不按秩合并)也基本够用,复杂度 O(\log n) 均摊;两者结合是 O(\alpha(n)) 近乎常数。docs/ds/dsu-complexity.md 有复杂度证明。

并查集应用:连通性判断、Kruskal 最小生成树(第 4 章)、判断图是否有环、离线处理询问。

ST 表

docs/ds/sparse-table.md。ST 表用 O(n \log n) 预处理,O(1) 查询区间最大/最小/ gcd 等可重复贡献的信息(但不能修改)。

for(int i=1;i<=n;i++) st[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)
  for(int i=1;i+(1<<j)-1<=n;i++)
    st[i][j]=max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
// 查询 [l,r]:
int k=__lg(r-l+1);
return max(st[l][k], st[r-(1<<k)+1][k]);
​

树状数组

docs/ds/fenwick.md。树状数组用 O(\log n) 支持单点修改 + 前缀查询。本质是分治:c[i] 维护长度为 lowbit(i) 的区间。

核心操作(x += lowbit(x) / x -= lowbit(x)):

void update(int i,int v){ for(;i<=n;i+=i&-i) c[i]+=v; }
int query(int i){ int s=0; for(;i>0;i-=i&-i) s+=c[i]; return s; }
// 区间 [l,r] 求和 = query(r) - query(l-1)
​

树状数组优势:代码极短、常数小(比线段树快 2-3 倍)。劣势:只能处理可减的信息(和、异或;不能直接 max)。逆序对是经典应用(离散化后按值建树状数组)。

学习建议

性价比最高的两个必学

💡 学习提示:如果数据结构只学两个,并查集 + 树状数组。两者代码都极短、应用极广、性价比无敌。并查集 20 行能写完,树状数组 30 行,但它们能解决的题目类型非常多。

学习顺序

按这个顺序,每个学完配套刷 5-10 题:

1. 栈、队列(BFS/DFS 的基础,先过)
2. 链表(理解即可,实际用数组模拟)
3. 单调栈、单调队列(滑动窗口、柱状图最大矩形等经典题)
4. 哈希表(理解原理,实战用 unordered_map 或离散化)
5. 并查集(重点!)
6. 二叉树、BST(线段树/平衡树的概念前置)
7. 二叉堆(会用 priority_queue 即可)
8. ST 表(RMQ 基础)
9. 树状数组(重点!)

学完这 9 个,再进第 02 节的线段树和 Treap。

配合 Wiki

每个结构 Wiki 页面都有:定义、过程图解、代码、复杂度分析、练习题。地图只做导读,真正的代码和图解在 Wiki 页面。读完这节知道每个结构是什么、用在什么场景后,去 Wiki 页面看完整实现。

常见误区

⚠️ 注意:

1. 并查集只写路径压缩不写按秩合并:其实够用,但要知道复杂度是 O(\log n) 而非 O(\alpha);追求严谨两个都写。
2. 树状数组下标从 0 开始:树状数组的下标必须从 1 开始,因为 lowbit(0)=0 会让 update 死循环。
3. ST 表用于可修改区间:ST 表不能修改,要修改用线段树。
4. 单调队列忘弹队首过期元素:滑动窗口移动时,要把超出窗口的队首弹出。
5. priority_queue 默认是大根堆:要小根堆写 priority_queue<int, vector<int>, greater<int>>。

本节要点

1. docs/ds/ 59 篇,本节覆盖基础:线性(栈/队列/链表/单调栈/单调队列)+ 哈希 + 树形(BST/堆)+ 并查集 + ST 表 + 树状数组。
2. 并查集 + 树状数组是性价比最高的两个必学,代码短应用广。
3. 并查集:路径压缩 + 按秩合并,近乎 O(1);用于连通性、Kruskal。
4. ST 表:O(n \log n) 预处理 O(1) 查询,不可修改。
5. 树状数组:单点修改 + 前缀查询 O(\log n),下标从 1 开始,处理可减信息。