今天是来海高（浙江海亮高级中学）的第三天。（怎么有种小学生日记的感觉……）
讲了「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扬）
最新评论