主席树

一句话理解

主席树常指可持久化权值线段树。

为什么要学

区间第 k 小。

讲解

root[i] 表示前 i 个数插入后的权值树。区间 [l,r] 用 root[r] 与 root[l-1] 相减。

例子

两棵树相减得到区间内的权值计数。

常见错误

• 没离散。
• l=1 时 l-1=0 的空树。