静态主席树

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

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

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

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

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

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

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

分类: 学习笔记

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注