高级数据结构（一）：并查集、树状数组、线段树基础
各位同学，今天我们来聊聊高级数据结构。说实话，刚入行那会儿，我觉得链表、栈、队列就够用了。直到有一次做网络设备的路由表管理，数据量一上来，O(n)的查找直接让CPU飙到100%。嗯，从那天起，我老老实实把并查集、树状数组、线段树这些家伙啃了一遍。
这三个数据结构，说白了就是解决三类经典问题：连通性判断、前缀和动态维护、区间查询与更新。它们各有各的脾气，但用好了，效率能提升一个数量级。
一、并查集：连通性的瑞士军刀
并查集解决什么问题？你想想看，社交网络里判断两个人是不是朋友的朋友，或者电路板里两个焊点是否连通。这类问题，并查集是首选。
它的核心思想很简单：每个元素都有一个"老大"（根节点）。两个元素连通，就把它们的老大合并。我习惯用数组来实现，下标代表元素，值代表它的父节点。
核心操作就两个：
- Find(x)：找x的根节点。路径压缩优化后，沿途节点直接挂到根上。
- Union(x, y)：合并x和y所在的集合。按秩合并，把矮树挂到高树下。
// 并查集基础实现 —— 我项目里常用的版本
#define MAXN 100005
int parent[MAXN];
int rank[MAXN]; // 秩，树的高度上界
void init(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int x) {
// 路径压缩：递归写法，简洁明了
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
// 按秩合并：矮树挂到高树下
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}我的经验：路径压缩和按秩合并一起用，时间复杂度几乎是常数。我曾经在一个嵌入式路由项目中，用并查集管理几千个网络节点的连通状态，每次操作都在微秒级完成。
避坑指南：我曾经犯过一个错——忘记初始化parent数组。结果find函数死循环，板子直接跑飞。记住：初始化时每个元素的父节点指向自己。
二、树状数组：前缀和的加速器
树状数组，也叫Fenwick Tree。说实话，我第一次看到这个结构时觉得挺巧妙的。它用数组模拟了一棵树，专门用来动态维护前缀和。
你可能会问：前缀和不是可以用普通数组吗？嗯，普通数组更新一个元素要O(n)重新计算前缀和。树状数组只需要O(log n)。
它的核心秘密就是lowbit操作：lowbit(x) = x & -x。这个操作能取出x二进制表示中最低位的1。比如lowbit(6)=2，因为6的二进制是110，最低位1对应2。
// 树状数组 —— 我调试过无数次的代码
int bit[MAXN];
int n;
void add(int idx, int delta) {
// 单点更新：从idx开始，向上传播
while (idx <= n) {
bit[idx] += delta;
idx += idx & -idx; // 关键：lowbit操作
}
}
int sum(int idx) {
// 前缀和查询：从idx开始，向左累加
int res = 0;
while (idx > 0) {
res += bit[idx];
idx -= idx & -idx;
}
return res;
}
// 区间查询 [l, r]
int rangeSum(int l, int r) {
return sum(r) - sum(l - 1);
}使用要点：
- 下标从1开始，0号位置不用。这是约定俗成的，方便lowbit计算。
- 树状数组只能处理前缀和类问题。区间最值？得用线段树。
- 更新和查询都是O(log n)，常数极小，比线段树快不少。
我的习惯：在嵌入式环境里，如果只需要单点更新+区间求和，我首选树状数组。代码量小，内存占用少，跑起来飞快。线段树虽然功能强，但代码量翻倍。
三、线段树：区间操作的万能工具
线段树，可以说是区间数据结构的"瑞士军刀"。它能处理区间求和、区间最值、区间更新……几乎你能想到的区间操作，它都能搞定。
它的思想是把一个区间不断二分，直到每个叶子节点代表单个元素。每个节点存储对应区间的信息（和、最大值等）。
// 线段树基础 —— 区间求和实现
#define MAXN 100005
int tree[MAXN * 4]; // 4倍空间，安全
void build(int node, int l, int r, int arr[]) {
if (l == r) {
tree[node] = arr[l];
return;
}
int mid = (l + r) / 2;
build(node*2, l, mid, arr);
build(node*2+1, mid+1, r, arr);
tree[node] = tree[node*2] + tree[node*2+1]; // 上推
}
void update(int node, int l, int r, int idx, int val) {
if (l == r) {
tree[node] = val;
return;
}
int mid = (l + r) / 2;
if (idx <= mid)
update(node*2, l, mid, idx, val);
else
update(node*2+1, mid+1, r, idx, val);
tree[node] = tree[node*2] + tree[node*2+1];
}
int query(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return tree[node];
}
int mid = (l + r) / 2;
int res = 0;
if (ql <= mid)
res += query(node*2, l, mid, ql, qr);
if (qr > mid)
res += query(node*2+1, mid+1, r, ql, qr);
return res;
}重要提醒：线段树数组要开4倍空间！我刚开始学的时候，开了2倍，结果数组越界，查了一下午bug。为什么是4倍？因为最坏情况下，树的高度是log2(n)，最后一层可能有2n个节点，总节点数不超过4n。
四、三者对比：什么时候用哪个？
| 数据结构 | 适用场景 | 时间复杂度 | 代码量 | 我的推荐 |
|---|---|---|---|---|
| 并查集 | 连通性判断、图论中的环检测 | 近似O(1) | 极小（20行） | 连通性问题首选 |
| 树状数组 | 单点更新+区间求和、逆序对 | O(log n) | 小（30行） | 求和场景首选 |
| 线段树 | 区间更新+区间查询、最值、复杂操作 | O(log n) | 较大（80行） | 功能复杂时用 |
我个人习惯是：能用并查集解决的，绝不用树状数组；能用树状数组的，绝不上线段树。为什么？代码越简单，bug越少，维护越容易。嵌入式环境里，代码体积和运行效率同样重要。
总结一下：
- 并查集：找老大，合并帮派。路径压缩+按秩合并，效率拉满。
- 树状数组：lowbit是灵魂，下标从1开始。求和快，但功能单一。
- 线段树：二分思想，4倍空间。功能全面，但代码量大。
这三个数据结构，是算法竞赛和工程实践中的常客。我建议你先把并查集和树状数组练熟，线段树可以慢慢啃。毕竟，一口吃不成胖子，对吧？