Skip to content
数据结构入门: 主席树

可持久化数据结构总是可以保留每一个历史版本,并且支持操作的不可变特性


概念引入

考虑一个经典的问题:

给定 n 个整数构成的序列 a,将对于指定的闭区间 [l,r] 查询其区间内的第 k 小值。

我们先考虑该问题的简化版本:

给定 n 个整数构成的序列 a,将对于指定的闭区间 [0,r] 查询其区间内的第 k 小值。

我们可以用线段树维护一个频数数组[1],然后在线段树上二分[2]

我们考虑这个简化问题和原问题之间的关系:

如果我们知道 [0,r][0,l1] ,然后两者的频数作差,就是在这个区间内的频数了,然后在此基础上二分即可

我们对原始数据按顺序更新频数数组

最暴力的想法是每次更新的时候都建立一个线段树,这样我们必然任意查询的 [0,r][0,l1] 的线段树,两者作差然后二分

但是这样显然空间会爆炸,每个线段树要4倍空间,q次操作需要q个线段树,这是不可接受的

如何利用空间呢?

还记得吗,线段树每次操作最多只影响logn个节点,所以其实我们很多节点是可以复用的,没有更新到的节点就直接指向原始位置即可,这就是可持久化线段树的核心思想

模板与练习

待更新

标注


  1. 也就是所谓的权值线段树 ↩︎

  2. 当然也可以直接维护对顶堆 ↩︎