Single

C++ 分块算法(暴力数据结构)

今天是来海高(浙江海亮高级中学)的第三天。(怎么有种小学生日记的感觉……)

讲了「C++ 分块算法」,简单总结一下,有兴趣的可以看一下,顺带整合一下,方便自己回顾学过的算法

0.什么是分块算法

分块查找是折半查找和顺序查找的一种改进方法,分块查找由于只要求索引表是有序的,对块内节点没有排序要求,因此特别适合于节点动态变化的情况。 ——Parsnip′s blog

按我的理解来说,我觉得分块就是暴力,而且是有智商的暴力。分块像什么?按我的想法,它像多线程,但又不完全是。具体是什么,等会仔细讲。

1.分块有什么用

降低时间复杂度,加快运行速度,但又特别好实现。这也是为什么叫做「暴力数据结构」的原因。

2.分块算法思想

为什么叫做分块,因为它分块啊。

简单来说,就是把一个数列分成多块,对其进行预处理(按照题目要求处理,统计啥的),之后方便统计、处理等。

3.具体实现

给定一个长度为 n 的数列,将其分成 \sqrt n 个块(别问我为什么是 \sqrt 2 个,我也不知道。想知道,自己去百度啊,度娘是万能的),对每个块进行统计等操作。

对于题目的询问区间,判断其包括其所包含的块,剩下未包含的区间用暴力搜索解决

4.分块优点

降低时间复杂度,原本O(n+qmn)的复杂度直接降到 O((m – n)q + n \sqrt{n} ),瞬间降了几个数量级

诶(眼睛放光),是不是可以暴力出奇迹,骗分拿省一啦(@某骗分大佬陈and扬)

参考文档:

https://www.cnblogs.com/Parsnip/p/10458689.html

https://www.cnblogs.com/mxrmxr/p/9912406.html

暂无评论

发表评论