前言：
首先，我们来考虑这样一个模型：有一段连续的序列a[1]~a[n]，然后现在我们需要执行几类操作：
出题人： 求出其中一段区间的和
智商180的某宝宝：哎呀，你怎么这么傻，直接记录这个序列的前缀和不就得了？
记录a[1]~a[i]的和为sum[i]，然后显然有sum[i+1]=sum[i]+a[i+1]，我们要求a[l]~a[r]就直接sum[r]-sum[l-1]呗。
出题人：区间加上某个值
由于某宝宝是大佬，两分钟后：我会一种叫线段树的东西(一种树形结构，可以维护区间求和和单点修改的优秀数据结构)！！！
出题人：查询一段区间上有多少个数<k (k>0且给定)
某宝宝：
出题人：对了，忘了告诉你了，k每次都不一样，还有，极其的多。另外，为了防止装*不让写平衡树(另一种能干很多事情的优秀数据结构)+线段树，占用空间不能超过****Mb
某宝宝:
下面就分享一个菜鸟也能懂得算法：分块
分块，顾名思义，就是把一段序列分成一小块一小块得来处理，维护。
我们把一段当成一个整体，只记录维护整体的有关信息，就是分块。
首先，对于前言说得那道题，很朴素的做法就是：
1.从询问区间的l到r扫过去，每回加上扫到的值，即$ans=\sum^{r}_{i=l} a[i]$
2.直接把$a[i]$重新赋值不就得了 a[i]=newa[i];
3.从询问区间的l到r扫过去,每回遇到<k的位置，答案+1
没错，这种做法很傻是不是？
但是，分块就是在这个基础上暴力优化的！！！
假设我们总共的序列长度为n，然后我们把它切成$\sqrt{n}$块，然后把每一块里的东西当成一个整体来看，
现在解释几个本文用到的术语：
完整块：被操作区间完全覆盖的块
不完整块：操作区间不完全覆盖的块
然后我们先看看怎么得出答案：
1.对于完整的块，我们希望有个东西能直接找出这整个块的和，于是每个块要维护这个块的所有元素的和。
.对于不完整块，因为元素比较少(最多有 总数n / 块数 = $\sqrt{n}$ 个) 这时候当n=1000000的时候最多有1000个，对比一下，我们可以直接暴力扫这个小块统计答案，
.小技巧：如果这个不完整块被覆盖的长度>块维护的长度的一半，何不用这个块的和-没有被覆盖的元素的值呢？
2.这里，我们换种思路，记录一个lazy 标记(为什么用lazy，因为我很懒),表示整个块被加上过多少了，
.对于完整块，我们直接lazy+=加上的数x,块内的和ans+=x*元素个数(因为每个元素都被加上了x)
.对于不完整块，直接暴力修改就好了，顺便可以把lazy标记清了。
3.哎呀，这个有点难度啊,
.要在每个完整块内寻找小于一个值的元素数，
显然我们不得不要求块内元素是有序的，这样就能用二分(快速在一个有序的序列里查询的一个算法),对块内查询。
.不完整的块暴力就好
.这样的话需要提前对每块里面的元素做一遍排序就好.
.但是当有修改的话，因为整个块同时加上(减去)一个数，每个数的相对大小是不会变的，但是如果是不完全块就会改变，这样的话，还是因为元素个数小，重新新排一下不就得了?
然后，这道题就用了一种看似高大上的方法做完了……比之前傻傻的暴力是不是好看很多呢？
在很多地方，我们可以运用到分块的思想，化零为整，把维护每个数的值变成维护一些整体的值，
一个很常见的例子就是：为什么班主任要给班里分组？因为他可不想收作业或者回执的时候一个一个收啊qwq交给组长然后组长在交给老师多好啊qwq
这样，我们就不用一个一个的找了qwq
然后就讲完基础了。
稍稍进阶：
其实，每一块可以维护的不止上面说的那几种东西，我们可以维护当前区间最大公约数是多少，最大异或和是多少……
客观的来说，分块是可以维护很多的，只要想出来怎么预处理，对于有修改的模型怎么维护，统计答案的时候怎么累加就行。
希望对大家有所帮助。
