分块学习

# 分块 ## 分块（第一节） ### 前记 最近学了分块（好奇怪啊，我先学线段树，树状数组，平衡树才开始学分块），为了不让自己忘记，也随便总结总结。因为刚刚开始入门，所以只讲最简单和最基础的。（以后会慢慢更新） ### 啥是分块妳 嗯~，其实分块是一种很暴力的算法，可以用于处理区间操作（主要）等问题，可以将线性的枚举优化。分块，就是**分很多块**来进行处理，和分治挺像的，不过分治分了再分，每次分两块(或更多)，而分块只用一次分很多块就可以了。 ### 分块的作用 上面已经说了，分块是用来优化枚举的，那怎么优化咧，就拿[P3374 【模板】树状数组 1](https://www.luogu.org/problemnew/show/P3374)来和大家讲一下。 #### 暴力做法 对于每个操作，我们直接将为该下标的数加x 。 对于每一个讯问，我们一个for过去统计。 这样这道题就做完了，可是这样的时间复杂度非常高，是O(NM). #### 分块做法 正解树状数组，不过这里讲分块。我们想一下怎么优化呢，对于每个操作，我们的复杂度是O(1)的，十分快;但是，对于每个讯问，复杂度却很高。那我们就从讯问入手，降低复杂度。 我们可以预处理每一个区间的和，前缀和就可以了，那修改操作会改变前缀和，怎么办呢？我们就可以引用分块思想，把这整个区间分成sqrt(n)块，将每一块的和先预处理出来，记为tag，那么每次操作，我们将要操作的那个数的所属块tag+=x，同时也对那个数直接修改。 讯问的话，我们查找[l,r]的区间和，如果有哪些块在[l,r]内的话，我们可以直接累加该块的tag。但有时候，区间[l,r]总有些数不完全是一整个块，那么我们暴力将那些数累加，每一次时间复杂度为O(sqrt(n))。 #### 时间复杂度证明 你说分块时间复杂度是O(sqrt(n))就一定是啊，那肯定不行，于是我们需要证明。 1、为什么要分成sqrt(n)块 理论上来说，这样分是最优的，为什么，因为如果分太多的话，直接累加块的tag的时候会变慢；有如果，分太少的话，暴力累加数的值会变慢；所以分成sqrt(n)块是最优的。 2、为什么讯问的复杂度是sqrt(n)的呢 讯问分成两个部分： （1）将整个块累加：块也就sqrt(n)个，所以最多sqrt(n)的复杂度。 （2）暴力将一个个数累加：如果是散着的数的话，数量一定小于一个块的大小，一个块的大小是n/sqrt(n)=sqrt(n)，所以时间复杂度最多是sqrt(n)（ps：要对区间两边都累加，所以有常数2） 那么总时间复杂度就是O(3 sqrt(n))。是不是快很多了呢！ #### 练习 一样的[【模板】树状数组 2](https://www.luogu.org/problemnew/show/P3368)也可以这么做。 对于每个操作，分块将区间[l,r]的整块tag+=x(tag初始为0)，再暴力将区间[l,r]两边不完全属于一个块的数累加值(tag不需累加)。 对于每个讯问，直接输出(该数的值+该数属于的块的tag值)就行了 [Loj #6277. 数列分块入门 1](https://loj.ac/problem/6277) [Loj #6277. 数列分块入门 1代码](https://www.luogu.org/paste/vact8sjv) #### 建议 最好去Loj上刷分块，那里有分块专题，~~还可以下数据~~，[Loj分块地址](https://loj.ac/problems/search?keyword=%E5%88%86%E5%9D%97) ## 分块（第二节） ### 前记 经过第一节的学习，大家应该都明白分块的基本思想了吧。下面第二节我将通过Loj上的分块专题来讲分块。 ### 开始学习 先看一下[这道题：数列分块入门 2](https://loj.ac/problem/6278) 一看题目，咦，求[l,r]区间小于c^2的数字个数，这不是很像求[l,r]区间c^2的排名吗，马上就可以想到平衡树啦，可是平衡树这么难写，那怎么办？ **分块！** 首先，我们一个一个步骤分着来看： (1).**操作** 操作和 分块1 的操作一模一样，我们先不理。 (2).**查询** 如果一般查询排名，我们可以将这一段数截出来，排序，然后二分查找(lower_bound操作)就ok了。那我们可不可以先将每一个块的数都排好序，然后查找每一个块的时候就直接二分呢？ ofcourse，当然可以！那零零散散的剩下的非整块的数就暴力找就可以了。 (3).**排序操作** 我们查询需要先排序，那么我们排序也成为了一个操作。我们另外开一个数组ve[i]（ve[i]为vector，i表示第i个块）来存每个块排序的数据（这里我使用了vector）。到时候查询的时候直接二分ve[i]就可以了。那每一次零散修改操作都会修改数值（整块操作还是直接加tag），那么我们要对有修改数值的那个块重新进行块内排序。 那么我们这个分块的基本思想就是这样了。还有很多小细节可以看看我的代码： [#6278. 数列分块入门 2代码](https://www.luogu.org/paste/oalf8poj) #### 练习 那么好，如果你学会了分块2并理解了，那么分块3对你来说简直是小菜一碟。 如果你真的不会的话（前提会分块2），我可以告诉你只需要修改讯问部分，如果你真的不行的话，说明你还没有真正理解分块2，再去看看吧下面，分块3代码（除了讯问部分我其他都不加注释，因为和分块2一样）：[#6279. 数列分块入门 3代码](https://www.luogu.org/paste/b92cz3sf) ## 分块（第三节） ### 前记 前面，我们学习了分块的许多操作，分块可以代替树状数组和平衡树的部分操作，那么线段树可不可以代替呢？ 分块的力量是巨大的，连平衡树都可以，小小的线段树怎么可能不行呢？这一节，讲线段树的分块做法！ ### 开始学习 那么先看看这道题：[#6280. 数列分块入门 4](https://loj.ac/problem/6280) 很明显，这简直是线段树的模板题（吓得我直接就用神威无敌线段树水过了），分块当然也可以完成。 我们还是分步骤看： (1).**修改操作** 又和分块1一样，不讲。 (2).**查询操作** 咦，这里是查区间和，分块1是查一个数，我们可以直接想到暴力将[l,r]区间所以数加起来，但明显超时。分块嘛，肯定是有作用嘀，我们可以马上想到提前把每个块的和都处理了，那么查询就十分方便了，两端暴力查，整块的就直接累加和就ok了。 嗯，很明显，这程序和分块1很像，但肯定被魔改过的，主要还是看程序的注释吧：[#6280. 数列分块入门 4代码](https://www.luogu.org/paste/fhczb0x8) #### 练习 然后我们就可以做[#6281. 数列分块入门 5](https://loj.ac/problem/6281)啦 看完是不是很懵逼，开方怎么打tag，打不了tag的话，分块就没啥用了啊，所以肯定是花式打tag的！**错**，就不打tag，就直接暴力！那要分块干嘛呀，等等你就知道了嘿嘿嘿~~（滑稽）~~ 先分析一下数据哈：有负数！！！负数怎么开方，明显开不了啊，这个······ 还有哈，0和1也是，怎么开都一个样…… 最大的数据2^31-1，这个开方开5次就变成1了…… 这……，是不是分析完数据觉得这题很滑稽呀 那么我们发现那些(<=1)的数修改起来简直是废的，除了耗时间什么用都没有。 我们就可以从这方面入手啊。 我们可以把那些小于等于1的数打标记，如果再搜到，不进行处理。那么一个一个打标记是几乎没有优化的，所以要一段一段打标记，所以就可以分块（怎么样，是不是完全想不到） (1).**修改操作** 修改呢，非整块就直接暴力对其进行开方，记得更新每块的和哦 \ QwQ /，而整块呢，我们下面讲整块操作。 (2).**查询操作** 暴力对非整块的数累加，整块的就累加那一块的和。 (3).**整块修改操作** 如果这一整块以前被打过标记，就退出，不然就暴力对块内数进行开方（记得更新每块的和），同时判断数是否小于等于1，如果都小于等于1就可以直接把这个块打标记了。 下面就可以看代码了：[#6281. 数列分块入门 5代码](https://www.luogu.org/paste/3vkaim7x) 未完待续……