# 1. Persistent Segment Tree 在区间历史版本回溯的工程实现。 A 每次更新会复制整棵树，因此总空间为 O(n²) B 历史版本一旦生成就无法再查询，只能用于当前版本 C 只有从根到被修改叶子路径上的节点被复制，其余节点与旧版本共享，总空间 O(n log n) ✓ 正确答案 D 可持久化线段树不需要额外空间，原地修改即可
# 2. Persistent Red-black Tree 在增删路径复制的工程实现。 A 所有节点都必须被复制，包括未修改的子树 B 被旋转/变色修改的节点必须在新版本中指向新复制的节点，避免破坏旧版本 ✓ 正确答案 C 红黑树无法持久化，因为旋转会破坏结构 D 复制路径时只需复制根节点即可
# 3. Persistent Segment Tree 在并查集按秩合并的持久化拓展。 A 路径压缩复杂度更高，无法达到 O(log n) B 路径压缩会大量修改 parent 数组，破坏可持久化的空间效率，而按秩合并保证 O(log n) 树高 ✓ 正确答案 C 按秩合并可以做到 O(1) 摊还 D 路径压缩在持久化场景下无法实现
# 4. Persistent Treap 在 implicit key 区间翻转的版本切换工程实现。 A 无旋 Treap 树高更小 B 无旋 Treap 不需要懒标记 C 无旋 Treap 的修改操作只有 split/merge，二者天然沿路径复制节点，不破坏旧版本 ✓ 正确答案 D 无旋 Treap 使用数组存储
# 5. Persistent Union-Find 在离线与持久化的 O(log² n) 工程实现。 A 两个都来自路径压缩 B 一个来自排序，一个来自扫描 C 一个来自按秩合并的树高 O(log n)，一个来自可持久化数组单点修改 O(log n) ✓ 正确答案 D 一个来自哈希，一个来自平衡树
# 6. 主席树（可持久化线段树）的建树与查询中静态区间第 k 小问题中，版本按前缀建立、查询时两棵树的差分如何工作？ A 版本 r 与版本 0 的节点之差 B 版本 l 与版本 l−1 的节点之差 C 版本 r 与版本 l−1 对应节点之和/差，得到区间 [l,r] 的统计 ✓ 正确答案 D 直接对整棵树求和
# 7. 主席树求区间不同元素个数中用上一次出现位置建树，查询 [l,r] 时如何统计？ A 每个值在第一次出现位置计数 B 每个值只在最后一次出现位置计数，从而区间和等于不同元素个数 ✓ 正确答案 C 每个值在全部出现位置计数 D 每个值不计数，只计数位置
# 8. 可持久化数据结构的空间分析中每次更新新建 O(log n) 个节点，n 次更新总节点数为何是 O(n log n)？ A 每次更新复制整棵树 B 所有节点都是独立新建的 C 更新次数 n 与树的大小无关 D 每次更新只复制 O(log n) 个路径节点，其余与旧版本共享，加上初始 O(n) 个节点 ✓ 正确答案
# 9. 可持久化并查集中如何用可持久化数组 + 按秩合并实现历史版本回退？ A 可持久化数组（存 parent/rank）+ 按秩合并 ✓ 正确答案 B 哈希表 + 路径压缩 C 链表 + 循环 D 堆 + 优先队列
# 10. 可持久化 Trie 的应用中如何支持历史版本的异或最大值查询，与可持久化线段树的空间差异？ A Trie 深度是二进制位数，线段树深度是值域的空间复杂度对数，两者都导致 O(n × 深度) 总节点 ✓ 正确答案 B Trie 完全不需要额外空间 C 线段树节点数是指数级 D Trie 深度是 log(log n)
# 12. Persistent Link-Cut Tree 在动态树路径查询的版本切换工程实现。 A LCT 没有旋转操作 B LCT 用数组存储无法持久化 C LCT 树高太高 D access 虚实切换涉及大量旋转与父子关系变更，路径复制需覆盖所有被改节点，与不可变诉求冲突 ✓ 正确答案
# 13. Persistent Union-Find 在 Clojure STM 事务的实现原理。 A 不可变持久化数据结构提供独立快照，冲突时回滚重试 ✓ 正确答案 B 全局互斥锁 C 事务日志 D 复制所有数据
# 15. 主席树在静态 K-th 区间离线持久化工程实现。 A 离散化后值域压缩到 n 以内，线段树深度 O(log n)，且第 k 小转化为值域计数二分 ✓ 正确答案 B 离散化能减少节点共享 C 离散化后无需建树 D 离散化让复杂度变成 O(1)
# 16. 可持久化 Treap 与 rope 中文本编辑器撤销/重做场景的数据结构选型？ A 每次操作生成新版本，回退只需切换根指针，O(1) ✓ 正确答案 B 撤销需要反向执行所有操作 C 可持久化版本无法定位字符 D 撤销需要复制整棵树
# 17. 主席树的空间优化中值域离散化与节点池（静态数组）的工程实现？ A 节点池必须用动态指针 B 离散化会增加节点数 C 值域离散化把深度从 O(log V) 降到 O(log n)，节点池用静态数组预分配避免动态分配开销 ✓ 正确答案 D 主席树空间无法优化
