首页 > 其他 > 详细

[学习笔记]二进制分组

时间:2019-02-24 12:42:28      阅读:187      评论:0      收藏:0      [点我收藏+]

说起来还是很简单的,就是分块暴力重构的思想

二进制分组就是把操作的数量二进制拆分,每个二进制位数用数据结构维护

合并的时候,暴力重构

每次查询,从logn个块依次用维护的数据结构查询

例如有23=16+4+2+1,再加一个操作,就合并成:24=16+8

查询的复杂度是logn*(每一块)logn其实是二进制下1的个数,比较虚。

暴力重构,如果重构的复杂度都是O(元素个数)的话,O(nlogn)

形象化理解,就是线段树从叶子开始建,儿子建满了就merge上去

 

一些操作因题而异,但是都是维护操作序列的感觉:
1.每次只是对前缀操作序列查询,重建之后还可以删除两个儿子

2.对操作序列的某个区间查询,线段树一样构造+查询即可

3.支持栈序删除操作,类似分块的删除,懒惰,如果凑成了1 1 1 1 ,才合并2 1 1,凑出2 2 2 2才合并4 2 2,这样,重构的元素大小和要再次删除

 

[学习笔记]二进制分组

原文:https://www.cnblogs.com/Miracevin/p/10425809.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!