题干与适用场景
请实现一个支持历史版本的整数数组结构。每次更新只修改一个位置，查询可以指定任意旧版本的闭区间和。要求旧版本不可变，说明坐标范围、时间复杂度、空间复杂度、版本分叉和测试策略。
这是一道偏难的数据结构题，考察递归分治、结构共享、不可变更新、边界处理和复杂度证明。题目假设数组长度固定，更新是单点赋值，查询是闭区间 [l, r] 求和。若需要区间加、删除或合并版本，应先说明那是不同的扩展。
面试官考察点
面试官希望看到候选人先确认“持久化”意味着旧根仍可查询，而不是复制整棵树。高质量实现会为更新路径创建新节点，复用未受影响的子树，并把每个版本的根保存起来。还要说明半开区间或闭区间约定、空查询、版本编号、负数、越界和空间上限。
回答前需要澄清的问题
- 数组长度和坐标是否固定？是否可以先做坐标压缩？
- 更新是赋值还是加法？是否允许同一位置重复更新？
- 查询区间是闭区间还是半开区间？空区间返回什么？
- 版本是否只能从最新版本追加，还是可以从任意旧版本分叉？
- 是否要求线程安全、持久化到磁盘或跨进程共享？
- 需要精确整数和，还是允许溢出检测或大整数？
- 版本数量和总操作数上限是多少？
30 秒回答框架
“我会把每个版本表示为一棵不可变线段树的根。单点更新沿根到叶复制 O(log n) 个节点，未经过的兄弟子树直接共享；查询从指定版本根递归，完全覆盖时返回节点和。根数组支持从任意旧版本分叉。建树 O(n)，每次更新与查询 O(log n)，总空间是初始节点加每次更新新增的 O(log n) 节点。我会用版本分叉、边界、负数和随机对照测试验证实现。”
分步骤深入解答
先固定不变量：节点覆盖一个明确的闭区间 [lo, hi]，sum 等于该区间当前版本的元素和；叶子覆盖一个位置；内部节点的和等于左右子节点之和；节点创建后不再修改。每个版本只保存一个根指针。
数组下标若是 0..n-1，可用递归建树。若输入是稀疏的大整数坐标，先收集所有可能坐标并压缩，再在压缩索引上建树；不要把巨大坐标范围直接展开成数组。
下面的伪代码使用赋值更新和闭区间查询：
Node { left, right, sum }
build(lo, hi, values):
if lo == hi: return Node(null, null, values[lo])
mid = floor((lo + hi) / 2)
left = build(lo, mid, values)
right = build(mid + 1, hi, values)
return Node(left, right, left.sum + right.sum)
set(node, lo, hi, index, value):
if lo == hi: return Node(null, null, value)
mid = floor((lo + hi) / 2)
if index <= mid:
nextLeft = set(node.left, lo, mid, index, value)
nextRight = node.right
else:
nextLeft = node.left
nextRight = set(node.right, mid + 1, hi, index, value)
return Node(nextLeft, nextRight, nextLeft.sum + nextRight.sum)
sum(node, lo, hi, ql, qr):
if qr < lo or hi < ql: return 0
if ql <= lo and hi <= qr: return node.sum
mid = floor((lo + hi) / 2)
return sum(node.left, lo, mid, ql, qr)
+ sum(node.right, mid + 1, hi, ql, qr)roots[0] 保存初始建树结果。若从版本 base 更新位置 i，创建 roots[next] = set(roots[base], 0, n - 1, i, value)。因此版本图是一棵根数组指向的有向无环共享结构，而不是线性历史链。版本分叉只需把任意旧根作为输入，不应把更新强制绑定到最新版本。
边界必须显式处理：n == 0 时不创建根；索引越界和 ql > qr 应返回结构化错误或按题目约定处理；查询区间可先裁剪，但不能悄悄改变调用者错误。计算 mid 时避免 lo + hi 溢出，在固定整数范围时可写成 lo + floor((hi - lo) / 2)。
初始建树需要 O(n) 节点和 O(n) 时间。每次单点更新只复制一条根到叶路径，因此新增 O(log n) 节点；查询访问 O(log n) 个规范区间，时间为 O(log n)。执行 u 次更新后的总空间是 O(n + u log n)，而不是 O(nu)。如果更新是区间赋值或区间加，仍可路径复制，但懒标记、节点合并和空间分析会改变。
节点不可变是正确性的核心。不要在更新时修改原节点的 sum 或子指针，否则旧版本会被污染。实现可以使用垃圾回收或引用计数；若需要手动释放，必须知道每个版本根的生命周期，不能因为删除一个版本就递归释放仍被其他版本共享的节点。
若只需要最近版本，普通线段树更简单。只有需要查询历史、回滚、分支实验或时间旅行时，持久化带来的空间成本才合理。若所有操作都是离线的，也可以考虑离线前缀或扫描线；回答应把数据结构选择和业务查询模式联系起来。
测试先用小数组穷举。每次更新后，用普通数组复制出新版本，并对随机版本、随机区间比较线段树结果。重点覆盖从版本 0 分叉、连续更新同一位置、负数、单元素、全区间、单点、空区间、最左和最右边界。再加入共享检查：更新一个位置后，另一侧子树的对象身份应保持不变。
测试还要验证版本不可变。保存每个旧版本的所有查询结果，执行多次分叉更新后重新查询；任何旧结果变化都说明节点被错误修改。对大规模操作统计节点数量，确认它接近初始 O(n) 加每次更新 O(log n)，避免意外复制整棵树。
高质量示范回答
“我先假设数组长度固定、更新是单点赋值、查询是闭区间求和，并且版本可以从任意旧版本分叉。每个节点覆盖 [lo, hi]，保存区间和；节点创建后不再修改。roots[v] 保存版本 v 的根。
建树时递归拆分区间。更新时沿根到目标叶复制路径：目标方向创建新子节点，另一侧直接复用旧指针，最后用两个子节点的和创建新父节点。查询从指定版本根出发，越界返回 0，完全覆盖返回节点和，否则递归左右子区间。
建树是 O(n) 时间和空间。每次更新新增 O(log n) 节点，查询和更新都是 O(log n)；执行 u 次更新后的总空间是 O(n + u log n)。旧根仍指向旧节点，所以任意旧版本都不会被新更新污染。若坐标很大，先做坐标压缩；若需要区间更新，我会重新评估懒标记和空间成本。
我会测试版本 0 分叉、连续更新同一点、负数、空区间和所有边界，并用普通数组作为随机对照。还会检查未受影响子树仍被共享，以及在新版本更新后旧版本查询结果保持不变。若只查询最新值，我会选择普通线段树，只有历史查询和回滚需求才承担持久化成本。”
常见错误
- 复制整棵树 → 每次更新变成 O(n) 空间 → 只复制根到叶的路径。
- 修改旧节点再保存新根 → 所有引用该节点的旧版本都会改变 → 节点创建后保持不可变。
- 把版本当线性链 → 不能从任意旧版本实验或回滚 → 根数组允许版本分叉。
- 忽略区间约定 → 闭区间与半开区间混用会产生边界错误 → 在不变量和函数签名中固定一种约定。
- 把大坐标直接建树 → 坐标范围远大于实际点数会浪费空间 → 先做坐标压缩或使用动态节点。
- 声称空间是 O(n) → 忽略每次更新都会新增路径节点 → 写出 O(n + u log n) 的总空间。
- 删除版本时递归释放共享节点 → 其他版本可能仍引用这些节点 → 使用引用计数或垃圾回收策略。
追问及应对
追问 1：如果更新是区间加，结构还成立吗？
可以路径复制覆盖更新区间访问的节点，并复制相关路径；若使用懒标记，标记也必须属于新节点，不能写入共享节点。新增节点数量可能是 O(log n) 到 O(log n 加覆盖节点数)，要根据实现给出边界，不能直接沿用单点更新的空间结论。
追问 2：如何支持查询两个版本之间的差异？
同时遍历两个根。若两个节点指针相同，该子树没有变化，可以直接跳过；否则继续向下或按聚合值计算差异。若要报告所有变化位置，复杂度还取决于输出数量。
追问 3：为什么不直接复制数组再做前缀和？
复制数组每次更新是 O(n) 空间和时间。若版本少且数组小，简单方案可能更合适；持久化线段树在大量版本、在线历史查询和局部更新下用 O(log n) 新增空间换取性能。
追问 4：版本根如何持久化到磁盘？
节点需要稳定 ID，子指针改为 ID，根表记录版本到根 ID 的映射。写入采用追加或写时复制，并在提交根之前保证新节点已持久化。恢复时先校验节点引用和根表，不能把内存地址直接序列化。
追问 5：如何证明旧版本不会被污染？
归纳每次更新：只有新节点被创建，任何旧节点的字段不变；新树只引用旧的未变子树和新建的变更路径。因此旧根可达的节点集合及其值保持不变。测试再用随机分叉对照验证这个不变量。