主席树

Vision271 · 2023-01-02 11:03:56 · 个人记录

概述

• 主席树，即可持久化线段树，指的是一种在动态开点线段树进行修改操作时建立一棵新的动态开点线段树来保存不同历史版本，并通过节点的合理复用来保证时空复杂度的数据结构。

• 这里我们只谈谈如何实现可持久化，和真正的“主席树”（可持久化线段树差分）相关的例题。

操作

• 主席树支持的操作，除一般线段树的操作外，主要是对历史版本的修改/查询。

复杂度分析

• 主席树的时空复杂度保证为 O((n+q)log_2\ m)。

实现原理

• 修改：

  • 建一棵新树，主要是要有一个新根。

  • 未修改的点直接连边（与原版本共用子节点）。

  • 修改过的点：

  • 用动态开点线段树的方式 ins 出来（同步地在原线段树和新线段树上走，以原线段树的节点为参考建出对应新节点）。

  • 标记永久化，与原线段树共用祖先节点和子孙节点。

  • 可以证明最多新建一条链，即单次时空复杂度都为O(\log_2 m)。

• 询问：

  • 无标记下传：同一般动态开点线段树。

  • 有标记下传：先以原子节点为参考建出新子节点，连边，然后标记下推。

例题

P3919 【模板】可持久化线段树 1（可持久化数组）

• 对一个数组，要求实现以下两个操作：

  • （1）在某个历史版本上单点修改，生成的新数组即为（修改次数 +1+1）版本。

  • （2）对某个历史版本单点询问。

• 这显然是个可持久化问题。

• 当然我们有一种邪道做法：给数组每个节点开一个 vector，然后丢一个 (val,his) 的结构体作为元素，修改直接加到队尾，询问的时候二分版本号，找一个不大于询问版本号的最大的。O(n\log_2 n)。

• 但这个二分非常难写，而且我们是来讨论主席树做法的。过！

• 我们注意到每次的修改量非常小，符合主席树要求。板子，过！

P3834 【模板】可持久化线段树 2

• 求静态意义下区间第 k 小。

• 第一反应是不是线段树维护桶然后二分？对，我一开始也是这么想的。可是这样维护的是全树的第 k 小，并且结果不可差分（你怎么知道 1\sim l-1 有多少个数 \leqslant l\sim r 的第 k 小）。其实很有道理，毕竟这里只满足结合性，不满足差分性。

• 唯一的好消息是静态，无修改。

• 考虑建主席树。

• 两种思路。

• 先谈第一种：区分值域查下标。

  • 以原数组为基建线段树。

  • 主席树之间的区别是这个数组最多容纳多大的数字（离散化后的）（预先写 pair(val,pos) 排序然后每次 ins）。

  • 每次询问时二分答案，check 一下第 now 棵线段树中 l\sim r 的元素够不够，够的话进一步下跳。直到找到第一个不符合条件的 now，则答案为 now+1。

  • 双 \log，n,m\leqslant 2e5，能过？

  • 经仔细思考（先证明再证伪再证明），实际上纸面复杂度是可以的（8\times 10^7 左右），开 \text{O2} 应该能创过去。

• 来看第二种：区分下标查值域。

  • 建树，数组为离散化后的桶。

  • 主席树之间的区别是这个桶对应的是原数组的 1\sim i。实现很简单，暴力 ins 就好。

  • 询问时，模仿线段树合并的思路：合并相当于相加，那我能不能相减？

  • 同步地在第 l-1 和第 r 棵上跑，算一下元素数量差够不够，树上二分。

  • 单 \log，美妙。

• 有没有想到什么？事实上，这道题确实线段树合并可做。先开一棵空树（第 0 棵），然后把第 i-1 棵合并到第 i 棵上，合并后 ins，询问完全一样。

• 这两种做法的差异就启示我们，对某些内外区分可以互换的题目，有时区分顺序非常重要，甚至影响到能否使用某些思想来加速。同时也启示我们，数据结构只是一种形式，思维不要受其局限，算法才是算法竞赛的核心。