高级数据结构（二）：线段树、树状数组、RMQ与LCA
好，咱们接着聊高级数据结构。上一章我们讲了堆、并查集和Trie树，这次要聊的这几个——线段树、树状数组、RMQ和LCA，说实话，是算法竞赛和工程性能优化里的“硬骨头”。
我个人习惯把这类问题归为“区间操作三件套”。你想想看，实际项目中，我们经常要问：某个区间的最小值是多少？ 某段数组的和能不能快速更新？ 树上两个节点的最近公共祖先是谁？ 这些问题，用朴素方法做，O(n)甚至O(n²)的复杂度，数据量一上来就崩了。
嗯，今天我们就一个一个把它们啃下来。
一、线段树（Segment Tree）
线段树，说白了就是一棵二叉树，每个节点代表一个区间。根节点是整个数组[1, n]，左孩子是左半区间，右孩子是右半区间。叶子节点就是单个元素。
我在项目中遇到过这样一个场景：一个实时监控系统，每秒要更新上千个传感器的数值，同时要查询任意时间段的平均值。用数组硬算？不行。用前缀和？更新太慢。最后我上了线段树，查询和更新都是O(log n)，稳得很。
线段树的基本操作
- 建树：递归构建，每个节点存储区间和（或最大值、最小值等）。
- 区间查询：从根节点开始，如果查询区间完全覆盖当前节点区间，直接返回；否则递归左右子树。
- 单点更新：找到叶子节点，更新值，然后回溯更新父节点。
- 区间更新（懒标记）：这是线段树的精髓。如果每次更新都递归到叶子，太慢了。懒标记的意思是：先记着“这个区间要加一个值”，等真正需要查询子区间时再下推。
// 线段树 - 区间求和（带懒标记）
#define MAXN 100005
int tree[MAXN << 2], lazy[MAXN << 2];
void push_down(int p, int l, int r) {
if (lazy[p]) {
int mid = (l + r) >> 1;
tree[p << 1] += lazy[p] * (mid - l + 1);
tree[p << 1 | 1] += lazy[p] * (r - mid);
lazy[p << 1] += lazy[p];
lazy[p << 1 | 1] += lazy[p];
lazy[p] = 0;
}
}
void update(int p, int l, int r, int ql, int qr, int val) {
if (ql <= l && r <= qr) {
tree[p] += val * (r - l + 1);
lazy[p] += val;
return;
}
push_down(p, l, r);
int mid = (l + r) >> 1;
if (ql <= mid) update(p << 1, l, mid, ql, qr, val);
if (qr > mid) update(p << 1 | 1, mid + 1, r, ql, qr, val);
tree[p] = tree[p << 1] + tree[p << 1 | 1];
}
int query(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[p];
push_down(p, l, r);
int mid = (l + r) >> 1, res = 0;
if (ql <= mid) res += query(p << 1, l, mid, ql, qr);
if (qr > mid) res += query(p << 1 | 1, mid + 1, r, ql, qr);
return res;
}
二、树状数组（Fenwick Tree / BIT）
树状数组，我更喜欢叫它BIT（Binary Indexed Tree）。它比线段树更轻量，代码更短，但能解决的问题范围也窄一些——主要就是单点更新 + 区间查询，或者区间更新 + 单点查询。
它的核心就一个函数：lowbit(x) = x & -x。这个lowbit能取出x二进制表示中最低位的1。树状数组就是靠这个来“跳”的。
// 树状数组 - 单点更新 + 区间求和
int bit[MAXN], n;
void add(int idx, int delta) {
while (idx <= n) {
bit[idx] += delta;
idx += idx & -idx;
}
}
int sum(int idx) {
int res = 0;
while (idx > 0) {
res += bit[idx];
idx -= idx & -idx;
}
return res;
}
// 区间[l, r]的和 = sum(r) - sum(l-1)
三、RMQ问题（Range Minimum Query）
RMQ，就是区间最值查询。给你一个数组，问任意区间的最小值（或最大值）。
解决RMQ问题，有几种思路：
- 线段树：O(log n)查询，O(n)建树，支持更新。
- ST表（Sparse Table）：O(1)查询，O(n log n)预处理，不支持更新。
- 树状数组：可以求最值，但实现起来比求和麻烦，不推荐。
我个人在静态数据（比如离线查询）中，特别喜欢用ST表。它基于倍增思想：st[i][j]表示从i开始，长度为2^j的区间的最小值。
// ST表 - RMQ
int st[MAXN][LOG], log2[MAXN];
void build(int arr[], int n) {
log2[1] = 0;
for (int i = 2; i <= n; i++) log2[i] = log2[i/2] + 1;
for (int i = 1; i <= n; i++) st[i][0] = arr[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
}
int query(int l, int r) {
int k = log2[r - l + 1];
return min(st[l][k], st[r - (1 << k) + 1][k]);
}
四、LCA问题（Lowest Common Ancestor）
LCA，最近公共祖先。给定一棵树，问两个节点的最近公共祖先是谁。
这个问题在项目里其实挺常见的。我记得有一次做社交网络的关系分析，需要判断两个用户是否在同一个“圈子”里，本质上就是找他们在组织树上的LCA。
解决LCA的常用方法：
- 倍增法：预处理每个节点的2^k级祖先，查询时先让深度大的节点往上跳，再一起跳。O(log n)查询。
- Tarjan离线算法：用并查集，一次DFS处理所有查询。O(n + q)。
- 树链剖分：把树剖成链，用线段树维护。适合需要同时处理路径查询的场景。
我个人最常用倍增法，因为它好写、好理解，而且在线查询。
// 倍增法求LCA
int up[MAXN][LOG], depth[MAXN];
void dfs(int u, int p) {
up[u][0] = p;
depth[u] = depth[p] + 1;
for (int j = 1; j < LOG; j++)
up[u][j] = up[up[u][j-1]][j-1];
for (int v : adj[u]) {
if (v != p) dfs(v, u);
}
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int j = 0; j < LOG; j++)
if (diff & (1 << j)) u = up[u][j];
if (u == v) return u;
for (int j = LOG-1; j >= 0; j--)
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
return up[u][0];
}
五、知识体系总览
下面这张图，是我自己整理的本章节知识结构。你可以把它当作一个“地图”，学完后再回来看，会更有感觉。
六、如何选择？
说实话，很多初学者会纠结“到底用哪个”。我的建议很简单：
| 场景 | 推荐数据结构 | 原因 |
|---|---|---|
| 区间求和，单点更新 | 树状数组 | 代码短，常数小 |
| 区间更新，区间查询 | 线段树（懒标记） | 树状数组做不了 |
| 静态区间最值查询 | ST表 | O(1)查询，快 |
| 动态区间最值查询 | 线段树 | 支持更新 |
| 树上两点路径问题 | LCA（倍增） | 好写，够用 |
好了，这一章的内容就到这儿。代码示例我都尽量精简了，你可以在自己的项目里直接套用。记住，数据结构这东西，光看没用，一定要动手写。我当年也是被线段树的递归搞到头大，但写个几十遍，自然就熟了。