进阶结构专题

环境：Windows 11 x64，GCC 13.1.0，g++ -std=c++17 -O2。每种结构都与朴素/暴力参照做过随机对拍。

一、并查集：一个优化就够，两个优化要分场景

int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }      /* 路径压缩 */
bool unite(int a, int b) {
    a = find(a); b = find(b); if (a == b) return false;
    if (rank[a] < rank[b]) std::swap(a, b);                        /* 按秩合并 */
    p[b] = a; if (rank[a] == rank[b]) rank[a]++;
    return true;
}

20 万个元素、20 万次随机合并 + 约 2.9 万次查找：

无优化（仅链式 find，随意挂接）   5091.2 ms（分量数 32601）
按秩合并                             4.2 ms（分量数 32601）
按秩 + 路径压缩                      4.7 ms（分量数 32601）

三个结论，第二个可能出乎意料：

不做任何优化的并查集是灾难：慢 1200 倍。随意挂接会让树退化成链，find 变 O(n)。
按秩合并单独就把问题解决了（5091ms → 4.2ms，树高被压到 O(log n)）。
在这个负载上再加路径压缩没有变快，甚至慢了 0.5ms。原因：树已经很矮（log n ≈ 18，实际平均深度远小于此），压缩的递归开销反而成了净成本。

路径压缩真正发力的场景是”查找远多于合并”（比如 Kruskal 里大量 find、网格连通性反复查询、离线询问）。所以两个优化都写上（它们互不冲突，最坏情况一起给出 O(α(n)) 的均摊界），但别以为只写路径压缩就够了——没有按秩/大小启发式，纯”路径压缩 + 随意挂接”的最坏情况仍是 O(log n) 均摊（这点学界有专门结论），而”只有按秩、无压缩”也是 O(log n)。

正确性验证：200 组随机小图（8 个点、随机边），把并查集的连通判定与 BFS 重建的连通分量逐一比对：

200 组小图与 BFS 连通性一致=1

并查集的 bug 通常是”没压缩/没按秩”（性能）或”忘了 find 直接比较父节点”（正确性）。后者经典表现为”看起来连通了但 p[x] != p[y]”——判断连通必须比较 find(x) == find(y)，不能比较 p[x] == p[y]。

工程要点：

加一个 sz[] 维护分量大小，能顺带解决”第 k 大连通块""带权并查集（食物链、银河英雄传说）”。
需要可回滚（离线动态连通性、带撤销的搜索）时不能用路径压缩（它改结构不可逆），只用按秩合并，这样每次修改只动一个点，能记录到栈里回退。
并查集不支持删除。要删除就离线倒序处理（把”删边”变”加边”）。

二、树状数组（Fenwick / BIT）：最短的代码解决两类问题

void add(int i, long long v) { for (++i; i <= n; i += i & -i) t[i] += v; }
long long sum(int i)         { long long s = 0; for (++i; i; i -= i & -i) s += t[i]; return s; }
long long range(int l, int r){ return l ? sum(r) - sum(l-1) : sum(r); }

i & -i 取最低位的 1，i += lowbit(i) 是”父节点”、i -= lowbit(i) 是”跳到前一个覆盖段”。

能力	朴素数组	树状数组	线段树
单点改 + 前缀和查	O(1) / O(n)	O(log n) / O(log n)	O(log n) / O(log n)
区间改 + 区间查	O(n)	需要两棵树（差分技巧）	O(log n)（懒标记）
代码量	—	~10 行	~50 行
常数	—	最小	中等
支持任意合并函数	—	只能可逆群运算	✅ 任意

选择原则：能用树状数组就别写线段树（代码少 5 倍、常数小、不易错）。需要”区间最值""区间翻转""可持久化”这类不可逆操作时才上线段树。

树状数组的第二个用途：求逆序对（边插入边查”已插入的比当前大的个数”），以及”第 k 小”（在树上二分）。

三、线段树 + 懒标记：区间修改的正确姿势

关键在懒标记的下推时机：只在”要进入子区间”时 push，且 push 时必须按子区间长度分配加值。

void push(int o, int l, int r) {
    if (lz[o] && l != r) {
        int m = (l + r) / 2;
        s[o*2]   += lz[o] * (m - l + 1);  lz[o*2]   += lz[o];   /* ← 乘左半长度 */
        s[o*2+1] += lz[o] * (r - m);      lz[o*2+1] += lz[o];   /* ← 乘右半长度 */
    }
    lz[o] = 0;
}

最常见的 bug 就是忘了乘长度——把 lz[o] 直接加到子节点的和上，结果在”区间长度 > 1”时全错。

实测（n=20000、20000 次随机”区间加 / 区间求和”交替）：

朴素区间操作        41.6 ms
线段树(懒标记)       5.5 ms（查询累加值 888737294898935）
朴素与线段树的查询累加值一致=1

“累加值一致”这一行比时间重要得多：它是唯一能证明懒标记下推正确的证据。线段树写错时通常不会崩，只会给出错误答案，而且在小数据上可能碰巧对。

其他易错点：

数组要开 4*n（不是 2*n），否则某些形态会越界。
mid = (l + r) / 2 在 l + r 溢出时会错，写成 l + (r - l) / 2。
递归版本在 n = 10⁶ 时深度约 20，安全；但函数调用开销大，性能敏感时写迭代线段树（2n 大小的数组，自底向上）。

四、字典树（Trie）：前缀问题的标准答案

第九节（串）已经用过 AC 自动机，这里补上纯 Trie 的账：

struct Node { int nxt[26]; int cnt; };      /* 每节点 26*4 + 4 = 108 字节 */

时间：查询 O(串长)，与词典大小无关。
空间：节点数 × 108 字节。英文小写 26 字母表下，100 万个平均长 8 的单词大约需要 ~50 万节点 ≈ 54MB（因为前缀共享）。字母表越大越吃亏：Unicode 直接开数组会爆，得用 unordered_map 或排序边表。
省空间手段：① 双数组 Trie（DAT，用两个 int[] 表示，缓存友好）；② 压缩 Trie（radix tree，把只有一个孩子的链合并）；③ 用 vector<Edge> 存孩子并二分。

典型用途：自动补全、IP 路由最长前缀匹配、敏感词、分词词典。

五、跳表：为什么 Redis 选它而不是红黑树

跳表是”多层有序链表”，期望 O(log n) 查找/插入，实现比平衡树简单得多：

struct Node { int key; std::vector<Node*> next; };   /* 随机层数：每层 1/2 概率 */

	跳表	红黑树
实现难度	低（几十行）	高（旋转 + 变色，易错）
范围查询	顺着第 0 层走，天然有序	中序遍历
并发	容易做无锁（只改局部指针）	难
内存	期望 2 个指针/节点	2 指针 + 1 bit
最坏	概率性的 O(n)（随机层数运气差）	严格 O(log n)

Redis 的 sorted set 用跳表，理由正是”好写 + 好做范围 + 并发友好”。在 C++ 里一般不需要自己写（std::map 够用），但看懂跳表对读并发数据结构代码很有必要。

六、LRU 缓存：链表 + 哈希的 40 行实现

struct LRU {
    size_t cap;
    std::list<std::pair<int,int>> order;                                  /* front = 最近使用 */
    std::unordered_map<int, std::list<std::pair<int,int>>::iterator> map;
    bool get(int k, int *out) {
        auto it = map.find(k); if (it == map.end()) return false;
        order.splice(order.begin(), order, it->second);                   /* O(1) 移到最前 */
        *out = it->second->second; return true;
    }
    void put(int k, int v) {
        auto it = map.find(k);
        if (it != map.end()) { it->second->second = v; order.splice(order.begin(), order, it->second); return; }
        if (order.size() == cap) { map.erase(order.back().first); order.pop_back(); }
        order.push_front({k, v}); map[k] = order.begin();
    }
};

实测 100 万次随机访问（键空间 3000、容量 1000）：

134.2 ms，命中 332977 / 1000000，当前大小 1000

约 134ns / 次操作，命中 33%（与键空间/容量的比例吻合：随机均匀访问下命中率≈1-容量/键空间≈0.67 才对……这里 33% 是因为未命中时代码走 put，put 里又占一次哈希查找，且 get+put 合计两次查找，所以统计口径是”get 命中”）。

这里踩了一个真实的 API 坑：list::splice 有三个重载，把单个元素移到同一个列表的前面必须写三参数版 splice(pos, list, it)。写成两参数版 splice(pos, *it) 会编译失败：

error: no matching function for call to 'list::splice(iterator, pair<int,int>&)'

（我第一版就是这么写错的，两处。两参数版的第二个实参是整个列表，不是元素。）

其他要点：

用 list 正是因为它的迭代器在 splice/push 后不失效，才能安全地存进哈希表。换成 vector 立刻全失效。
生产环境要加锁（分片锁）、要支持 TTL、要考虑 LFU/ARC 等替代策略。
map 的 value 是迭代器，所以删除时必须两边同步——任何一处忘记同步就是内存泄漏或悬空迭代号。

七、这一节的自查清单

并查集：判断连通比较 find(x)==find(y)，不是 p[x]==p[y]
需要回滚/撤销时只用按秩合并，禁用路径压缩
区间加 + 区间和优先想树状数组（差分两棵树），再考虑线段树
线段树懒标记下推要乘子区间长度；数组开 4n；mid 用 l+(r-l)/2
任何树形结构都要与朴素数组/BFS 做随机对拍，比对查询结果累加值
Trie 的节点大小按字母表算账，Unicode 不要开定长数组
LRU 用 list 是为了迭代器稳定；splice 单元素要用三参数版
需要”有序 + 范围查询 + 简单实现”时评估跳表，但 C++ 里优先 std::map
结构选型的第一个问题是”支持不支持我要的操作”，第二个才是复杂度，最后才是常数

数据结构与专栏 12 节到此完结。 下一大类是并发编程：线程与进程、互斥锁与临界区、条件变量与等待通知。