主席树学习记录

主席树

概念

主席树就是可持久化并查集。

主要用于求区间第k大值。

也就是压缩的权值线段树。

思路

首先，枚举(k)，求出(n)个(1sim k)。

因为每次都开一个权值线段树肯定爆空间，我们发现，他们都会有一个相同的部分，而且随着k的增大，相同的部分就越多。所以我们想办法把后面的东西建立在前面的基础上。于是我们想到了用主席树。

代码

先咕咕了，目前还不是很熟悉。