[学习笔记]二进制分组

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

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

合并的时候,暴力重构

每次查询,从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,这样,重构的元素大小和要再次删除次数级别相等。就是常数大。

毕竟属于可以暴力重构的东西,对于每组的数据结构灵活性要求就不高了,甚至不用随机插入

而且这玩意在线算法

 例题:

bzoj2989&&4170数列——二进制分组+主席树

主席树众所周知难以随机插入,但是配合上二进制分组,暴力重构就解决了问题

CF710F String Set Queries

 

体现了强制在线下二进制分组的好处,cdq虽然在操作序列的时间上可以降维打击,变成先插入删除再查询,但是毕竟只是离线算法

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