主席树(可持久化线段树)

定义

主席树是可持久化权值线段树的俗称,因提出者黄嘉泰的拼音缩写与"主席"相同而得名,在中文算法竞赛圈广泛流传。它对序列每个前缀各建一个版本的权值线段树,新版本仅复制被修改的 O(log n) 个节点,其余节点与旧版本共享。

原理

第 i 个版本的线段树统计前 i 个元素的值域分布。由于线段树节点信息可差分,用版本 r 与版本 l-1 对应节点相减,即得区间 [l, r] 的值域信息,再在树上二分即可回答"区间第 k 小"等查询。空间复杂度 O(n log n),单次查询 O(log n)。

应用

典型问题包括静态区间第 k 小、区间内某值出现次数、区间不同数个数(配合技巧)等;结合树上差分可扩展到树路径查询;数据库与时序系统中的多版本快照思想与之同源。

优缺点

优点是支持在线查询、无需离线排序、思想可推广到各类可差分信息;缺点是空间开销较大,动态修改需要再套树状数组,实现复杂度上升。