主席树与它的板子

__ryp__ · 2024-02-20 21:52:17 · 个人记录

主席树就是可持久化权值线段树。因为线段树本身就比平衡树常数小，并且它是严格 \Theta(\lg n) 而不是摊下来的，所以说 “能离线的都用线段树” —— 崔神语。

主席树板子是区间的第 k 小问题，P3834。读一下题，你会发现这题甚至都没有在不在线的区别。

我们先考虑怎么维护 [1, r] 内的第 k 小。这就和平衡树的 kth 差不多。建一个值域线段树，对区间维护一个 sum，表示区间内有多少个数。那么显然，我们只需要根据当前区间数的数量来判断走左还是右子树即可，单查询 \Theta(\lg n)，总复杂度 O(n\lg n + q\lg n)，因为带了一个离散化。

再考虑 [l, r] 的第 k 小。这玩意儿一般人按说是没法忍住不继续看下文的情况下能自己想出来的。我们用可持久化线段树维护每一个历史版本，然后 [l, r] 的查询就变成了个前缀和，同样复杂度可做，但是空间从 O(n) 到了 O(n + q\lg n)。

模板懒得写了，随便抄个题解就过了。