静态主席树

作者: MayFlyyh 分类: 学习笔记 发布时间: 2018-06-16 00:03 ė 6 没有评论

静态主席树

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

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

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

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

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

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

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

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/229

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部