主席树(洛谷P3834)

在 mwh 大佬的指引下,我最近学习了主席树。

思想

主席树是一种特殊的线段树,能够存储线段树的历史版本,我们称这种性质叫做可持久化。

主席树的可持久化通过这样来实现:我们每次修改单个节点,必然只会经过 $log_2n​$ 条“线段”,对于这些线段,我们都新开节点来存储。显然对于每一次修改操作,根节点都会被新建。那么我们只要存储下来每一次修改说对应的根节点即可。空间占用 $O(n log n)​$

具体思路可参考 https://www.luogu.org/blog/LonecharmRiver/zhu-xi-shu ss中的图片。

关于模板题

我们要维护静态区间第 k 小。可以先把数组离散化,比如:

1
2
3
离散化前 4 1 1 2 8 9 4 4 3
离散化后 4 1 1 2 5 6 4 4 3
离散数组 1 2 3 4 8 9

我们根据离散数组作为所维护的区间。第 i 棵树存储 [1, i] 内各数值出现的次数。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×