15.1 高级数据结构导览
前置：数组、哈希表、树与渐进分析。第 15 章按概率成员关系、增量连通性和动态区间聚合展开三种结构。
这里没有一项“更强”的万能结构，只有三类约束不同的任务：
- 权威名单太大，先用很少的内存挡住确定不存在的查询；
- 边持续增加，只问两个节点是否已经连通；
- 数组中的数值不断修改，同时反复查询区间总和。
三份需求分别对应布隆过滤器、并查集和线段树。它们没有共同的“高级接口”，只有更具体的取舍。
三条学习路线
布隆过滤器：概率成员关系
布隆过滤器不保存元素本身，只保存若干哈希位置。它允许假阳性，用紧凑的位数组换取空间节省；在插入完整生效、没有丢失位更新且配置一致的前提下，不产生假阴性。
这一篇会推导误报率与参数关系，实现真正按 bit 存储的过滤器，并解释为什么普通版本不能删除。适合先修哈希表之后阅读。
并查集：增量连通性
并查集只保留集合代表元，不保存两点间的路线。路径压缩和按大小合并让一长串 find/union 操作具有 O(α(n)) 的摊还成本。
这一篇实现 find、union 和 connected，验证重复合并、分量数量与集合大小，并说明它在 Kruskal 和离线连通性中的职责边界。
线段树：动态区间聚合
线段树把数组区间的聚合结果存在树节点中。点更新只重算一条祖先链，半开区间查询拼接 O(log n) 个摘要。
这一篇明确处理空输入与非法区间，使用迭代数组布局，并把 lazy propagation 留在“先定义更新代数”的边界之后。
Trie 为什么不在这里重复
Trie 已在字符串匹配章节讲过完整词、公共前缀、字符集合同和空间取舍。高级数据结构不等于同一实现重复出现；需要自动补全时可从那里继续：定位前缀节点后，还要遍历后代、收集完整词，并规定排序和返回数量；原示例只判断前缀是否存在。
如果目标是 IP 最长前缀匹配，还需要二进制或压缩 Trie、地址位宽和路由优先级等新合同，不能从小写字母 Trie 直接推出。
选结构前先问什么
| 问题 | 关键提问 | 常见起点 |
|---|---|---|
| 成员关系 | 能否容忍误报？需要枚举或删除吗？ | Bloom / hash set |
| 连通性 | 边只增加吗？需要具体路径吗？ | Union-Find / 图搜索 |
| 区间查询 | 数据静态还是动态？更新点还是区间？ | 前缀和 / Fenwick / segment tree |
| 前缀查询 | 字符集、规范化和返回顺序是什么？ | Trie / 有序索引 |
先写接口和错误容忍度，再谈复杂度。把结构名字倒过来套需求，往往会漏掉删除、顺序、精确性或更新模式。
卷末练习
- 为同一批 key 同时建立 hash set 与 Bloom filter，比较实际内存和误报。
- 为连通无向图实现 Kruskal，再用图遍历验证所选边连通全部顶点；输入不连通时应返回怎样的森林？
- 用前缀和与线段树处理同一操作序列，找到更新比例的性能分界。
- 为三个结构分别写一句“不适合做什么”，比应用清单更能检验理解。
从数组到图，再到概率过滤、增量连通和动态区间，结构的价值都来自同一件事：为特定查询保留足够的信息，同时放弃不需要的能力。放弃了什么，决定了它不能回答的问题。
接着阅读布隆过滤器，按三条路线完成这一章。下一卷进入计算机系统。在那里，抽象数据类型会落到字节、缓存、指令与进程上；算法复杂度仍然重要，但内存层次和机器边界也开始参与答案。