静态主席树

静态主席树

维护区间查某个数的存在次数或者第k大以及更多

可持久化线段树+权值线段树

可持久化线段树，每次修改logn个节点包含当前需要修改的点x的区间，从前一个中继承剩下无需修改的区间

主席树查询：用区间下标root[r]-区间下标root[l-1]的结果查询

比如一个数在r以内的出现次数为x，在l-1以内的出现次数为y

那么在l-r区间内出现的次数就是x-y，大概是这个原理吧

权值线段树，把线段树的下标当作数字，统计出现次数(通常需要离散化)