persistent segment tree · 前缀版本 · 值域作差

可持久化线段树与区间第 k 小

静态数组上反复问「区间 $[l, r]$ 里第 $k$ 小的数是多少」，朴素做法是把区间切出来排序，单次 $O(len \log len)$ 。区间长度上万、查询上万次时这条路走不通：实测 10 万长的数组、1 万次随机区间查询，切片加排序折算下来要 24.8 秒。

本页给出的解法只需要上一页的一个结论：一次单点修改只新建 $O(\log n)$ 个节点，旧版本原样可用。把它用在值域上，「区间的值分布」就成了两个版本的差。

1 · 版本即前缀

换一个统计口径：不建下标上的线段树，而建值域上的计数线段树——第 $v$ 个叶子存「值 $v$ 出现了几次」，内部节点存子树的计数和。

定义 1.1（persistent segment tree 的前缀版本） 设数组为 $a[1..n]$ ，值域为 $[0, m)$ 。令 $T_0$ 为全零的计数树， $T_i$ 为在 $T_{i-1}$ 上把值 $a[i]$ 的计数加一得到的新版本。则 $T_i$ 恰是前缀 $a[1..i]$ 的值分布，且 $T_0, \dots, T_n$ 共存。

这一族版本能存下来，靠的是每一步只新建一条路径。空树用 null 表示，插入沿途按需新建，一次插入的新建量是 $\lceil \log_2 m \rceil + 1$ 。 $n = 10^5$ 、 $m = 131072$ 时，全部 100001 个版本合起来是 1800000 个节点；同样多的版本若各存一棵满树要 $2m - 1 = 262143$ 乘以 100001，约 262 亿个节点，差 14564 倍。

注 · 中文社区把这个结构叫「主席树」，来源是提出者 fotile96 的姓名首字母缩写与当时的一个玩笑，与结构本身无关。英文文献里它没有单独的名字，就叫 persistent segment tree。

值域必须有界且不太大，否则叶子数吃不消。实际用法是先做一次 coordinate compression：把 $n$ 个值排序去重，用它们的名次当值域，于是 $m \le n$ 。引擎里没有做这一步，输入直接要求落在给定的 $[lo, hi]$ 内——这是刻意的取舍，为了让 lab 里的值域坐标与页面上的数字对得上。

2 · 两个版本作差

计数是可加的，所以区间 $[l, r]$ 的值分布就是 $T_r$ 减 $T_{l-1}$ 。关键在于这个减法不必真的逐格做： $T_r$ 与 $T_{l-1}$ 的节点在树上一一对位（同一个 $[lo, hi]$ 区段的节点在两棵树里都在同一个位置），下探时对位相减即可。

图 2-1 · 值域上每个格子的计数，左边是前缀 l−1，右边是前缀 r，两者之差就是区间内的出现次数。可调 l 与 r 观察差值随区间伸缩变化，也可换 seed 换一组数据。

对位这件事之所以成立，正是因为两棵树共享了大量节点： $T_{l-1}$ 与 $T_r$ 的不同之处只在 $a[l..r]$ 这 $r-l+1$ 次插入所触碰的那些路径上，其余子树是同一批对象。共享既省了空间，也让「减法」在共享处直接归零。

3 · 下探找第 k 小

有了对位相减，找第 $k$ 小就是一次从根到叶子的下降。在当前值域段 $[lo, hi]$ 上，令 $c$ 为左半段在区间内的元素个数（右版本的左孩子计数减左版本的左孩子计数）。若 $k \le c$ ，答案落在左半， $k$ 不变；否则落在右半， $k$ 减去 $c$ 。

图 3-1 · 一次区间第 k 小查询的逐层下探，表格给出每层的左半计数与走向，下方色带显示值域被逐层砍半。可调 k 观察走向翻转的临界点。

每层一次减法、一次比较，总代价 $O(\log m)$ ，与区间长度无关。 $m = 10^5$ 时下探 17 层。实测 10 万长的数组、1 万次随机区间与随机 $k$ ，查询总耗时 21.7 ms；同一批查询用切片加排序折算是 24782 ms，差 1142 倍。答案逐条核对一致。

4 · 与普通线段树的分野

线段树 · 区间查询与单点修改里的线段树只有一棵，随时间演化：update 就地改沿途节点，改完就回不去了。它回答的是「当前数组在区间 $[l, r]$ 上的聚合」。

本页的树每次修改留下一个新根， $n$ 个根并存。它回答的是「前缀 $i$ 的值分布」，而任意两个前缀相减给出任意区间的值分布。两者的下标含义也不同：普通线段树的叶子是数组下标，本页的叶子是值域坐标。

换句话说，可持久化把「时间」这一维从破坏性变成可寻址：版本号成了一个可以随便取用的下标。区间第 $k$ 小只是这个能力最直接的一个用法，同一套结构还能回答区间内小于某值的个数、区间内不同值的个数（配合「上一次出现位置」的版本轴）等一族问题。

5 · 统计口径的一个坑

写这一页时统计「全部版本合起来有多少节点」，最初的写法是对每个根做一次可达集遍历再取并集。这在 1000 个版本上跑得很快，换到 100001 个版本直接卡死：第 $i$ 个版本的可达节点数是 $O(i \log m)$ ，逐版本遍历的总代价是 $O(n^2 \log m)$ ， $n = 10^5$ 时是 $10^{11}$ 量级。

正确的口径是把每次插入返回的 created 累加——因为路径复制保证了「新建的节点此后不会再被任何后续版本新建一次」，累加值恰好等于并集大小。改完之后同一个测量降到 80 ms。这个坑值得记下来：结构共享让「总量」无法用逐版本求并来算，只能在生成时记账。

6 · 参考文献

Sarnak, N., & Tarjan, R. E. (1986). Planar point location using persistent search trees. Communications of the ACM, 29(7), 669–679.
Driscoll, J. R., Sarnak, N., Sleator, D. D., & Tarjan, R. E. (1989). Making data structures persistent. Journal of Computer and System Sciences, 38(1), 86–124.
Chazelle, B. (1988). A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing, 17(3), 427–462.
可持久化线段树. OI Wiki. oi-wiki.org/ds/persistent-seg/