块状结构

xiaoxiao2021-02-28  7

作为一名资深蒟蒻,在OI比赛中想出题解为不可能事件,所以蒟蒻就须掌握一些高效的骗分方法

块状结构以 n \sqrt n n 的较低复杂度和多功能以及“短”代码博得众多蒟蒻的欢迎

目前蒟蒻只知道三类块状结构:块状数组(分块),块状链表,块状树

块状数组(分块)


①分块

分块最直观的就是将一段区间分成若干块,每个块内拥有较多的数据,当需要集体修改时可以直接标记,当需要取出其中的元素时再将标记下推

至于修改与查询操作

主要就是像线段树一样(只不过分块像一个只有两层的线段树) 如果修改区间覆盖当前块直接打标记或直接调用这个块的总值(区间的中间部分) 如果区间和当前块没有包含关系且有交集,则暴力修改 (区间的两边边缘部分)

所以根据以上原理,最坏情况下的时间复杂度为 O ( 块 的 数 量 + 块 的 大 小 ) O(块的数量+块的大小) O(+) ,由于块的数量和大小乘积一定,所以当块的大小取 n \sqrt n n 时复杂度最小为 O ( n n ) O(n \sqrt n) O(nn ),在部分情况下可以骗取大部分分数,对于本蒟蒻来说已经很棒了

例题:线段树能做的题其实都可以用分块做,只是速度慢一点

②分块 n \sqrt n n 思想

如洛谷P3396

这题中是当模数小于 n \sqrt n n 时,用从小到大的模数预处理;若大于,则暴力取和

核心思想:小数据 n \sqrt n n 从小到达处理,大数据 n \sqrt n n 从大到小处理,总复杂度并不会超过 n \sqrt n n

块状链表

关于这一块,强烈建议看看

王悦同2014年国家集训队论文——《根号算法——不只是分块》 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 苏 煜 2008年国家集训队论文——《对块状链表的一点研究》

里面真的说的很清楚,我就不再多说了

块状树

其实可以套用到所有树上面,只用把每一个节点换成一个块就行了,可以降低复杂度

但好像如果暴力维护块的大小,速度会慢?

转载请注明原文地址: https://www.6miu.com/read-1400031.html

最新回复(0)