说起来还是很简单的,就是分块暴力重构的思想
二进制分组就是把操作的数量二进制拆分,每个二进制位数用数据结构维护
合并的时候,暴力重构
每次查询,从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