静态主席树 维护区间查某个数的存在次数或者第k大以及更多 可持久化线段树+权值线段树 可持久化线段树,每次修改logn个节点包含当前需要修改的点x的区间,从前一个中继承剩下无需修改的区间 主席树查询:用区间下标root[r]-区间下标root[l-1]的结果查询 比如一个数在r以内的出现次数为x,在l-1以内的出现次数为y 那么在l-r区间内出现的次数就是x-y,大概是这个原理吧 权值线段树,把线段树的下标当作数字,统计出现次数(通常需要离散化) 分类: 学习笔记 标签:学习笔记 0 条评论 发表评论 取消回复您的电子邮箱地址不会被公开。 必填项已用*标注 名称 * 电子邮件 * 网站 在想些什么? 在此浏览器中保存我的显示名称、邮箱地址和网站地址,以便下次评论时使用。
0 条评论