1. Persistent Segment Tree 在区间历史版本回溯的工程实现。
问题
请详细说明可持久化线段树（主席树）在区间历史版本回溯场景下的工程实现原理，包括建树、版本更新与回溯查询的具体做法？
考察点
- 可持久化的核心思想：路径复制（Path Copying）与节点共享
- 版本管理：每个版本对应一个根节点，历史版本可随时回溯
- 时间与空间复杂度：O(log n) 单次操作，O(n log n) 总空间
答案
可持久化线段树的核心是"路径复制"：每次更新时，只新建从根到被修改叶子这条路径上的 O(log n) 个节点，其余节点与旧版本共享。因此每个版本用一个指针（根节点）唯一标识，历史根节点被保留，随时可以沿着它查询当时的区间状态。工程上节点通常用数组 + 下标来模拟指针（避免动态指针的分配开销），每个节点存左右孩子下标与该节点维护的聚合信息。建树时先建一棵空树（版本 0），在此基础上每次修改生成新版本并把新根保存到 roots 数组。查询时直接传入对应版本的根即可，与版本无关的节点天然被共享，从而保证总空间 O(n log n)。
解析
之所以能压缩空间，是因为单次修改只影响从根到叶的一条路径，其余子树完全不变。路径复制让新旧版本共享那些不变子树，既保证了不可变性（旧版本数据不被破坏），又实现了数据复用。这是所有可持久化（persistent）数据结构统一的设计范式，也是主席树能处理"询问历史区间"问题的空间基础。
示例代码
class PersistentSegTree {
static class Node { int l, r, sum; } // 左/右孩子下标，聚合和
Node[] tr; int tot;
int build(int l, int r) { // 建空树
int p = ++tot;
if (l != r) {
int m = (l + r) >> 1;
tr[p].l = build(l, m);
tr[p].r = build(m + 1, r);
}
return p;
}
int update(int prev, int l, int r, int pos, int val) { // 路径复制
int p = ++tot;
tr[p].l = tr[prev].l; tr[p].r = tr[prev].r; tr[p].sum = tr[prev].sum;
if (l == r) { tr[p].sum += val; return p; }
int m = (l + r) >> 1;
if (pos <= m) tr[p].l = update(tr[prev].l, l, m, pos, val);
else tr[p].r = update(tr[prev].r, m + 1, r, pos, val);
tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum;
return p;
}
int query(int l, int r, int L, int R) { /* 区间和查询 */ }
}