在一次的luogu比赛后，问学长一道题的做法，学长说了句分块，那是第一次听说分块，那道题我的第一直觉是线段树可是我线段树不好写不出来，学长的一句分块让我有了一种用分块代替线段树的想法。我在网上搜博客的时候看到了hzwer大神的分块练习1~9某位博主说从学习开始四天做完这九道题，我就暗下决心怎么样四天之内也要写完吧，最好更快。然而现在我心态爆炸，已经没有心情继续写下去，所以原定写完九道题再写的总结，还是在我忘掉之前写完吧。。。。。。
希望退役之前我可以把1~9写完吧。
分块，说白了就是大暴力，把原来的区间分成一块一块的，区间修改时把包含在这个区间中的各个块进行标记修改，不在一整块中的部分即最左端和最右端进行暴力修改，（例如：在9个数的序列中修改第2位到第7位，
9个数可以分为3块（一般每个块的长度均为根号下n，我也不知道为什么，只知道这样操作确实快，唉，我太弱了） ，每块长度为3，
那么2在第一块,7在第3块，
所以从2开始修改，
修改到其所在块的最右端，接着一整块都包含在修改区间内，
所以标记此块，而到下一块我们发现我们需要修改的区间此块只包含7，所以我们只修改7）
对于这样处理起来可以节省很多时间，这就是分块，时间复杂度o(√n)。
在loj上有hzw的九道数列分块入门题
每道题的难度显而易见了
数列分块入门1：
操作：区间加法，单点查值
线段树和树状数组都可以进行的经典操作，而分块怎么进行呢，其实就和上面的讲解一样，定义一个标记数组存储下区间内每个数需要修改的值，对于直接暴力的地方（如：上面的2，3和7）直接在原数组上修改，输出时需要记得加上标记数组中的值。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
inline long long read(){//读入优化
long long x = 0; long long f = 1; char c = getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int n;
int m;
int opt,l,r,c;
int z[500521];//原数组
int pos[500521];//存储每个点所在的块
int tag[500521];//标记数组
void modify(int l,int r,int c){
if(pos[l] == pos[r])//如果在同一个块内
//直接暴力修改
for(int i = l; i<=r; i++)
z[i] += c;
else {
//修改右边不在一整块中的部分
for(int i = l; i<=pos[l]*m; i++)
z[i] += c;
//标记每个块需要加上的值
for(int i = pos[l]+1; i<=pos[r]-1; i++)
tag[i] += c;
//修改左边不在一整块中的部分
for(int i = (pos[r]-1)*m+1; i<=r; i++)
z[i] += c;
}
}
int main(){
n = read();
m = sqrt(n);//开方操作，确定每块的长度，sqrt在math库中需要加上
for(int i = 1; i<=n; i++) z[i] = read();
for(int i = 1; i<=n; i++) pos[i] = (i-1)/m+1;//计算每个点所在的块可以算一下进行证明
for(int i = 1; i<=n; i++){
opt = read();
if(opt == 0){
l = read();
r = read();
c = read();
modify(l,r,c);
}
if(opt == 1){
l = read();
r = read();
c = read();
//最后输出的值就是该点的值加上该点所在块的标记值（即需要加上的值）
printf("%d\n",z[r]+tag[pos[r]]);
}
}
return 0;
}
其中修改操作为了简便也可以这样写
void modify(int l,int r,int c)
{
//修改左边不在区间中的部分
for(int i=l;i<=min(pos[l]*m,r);i++)
z[i]+=c;
//修改右边不在区间中的部分
if(pos[l]!=pos[r])
for(int i=(pos[r]-1)*m+1;i<=r;i++)
v[i]+=c;
//修改中间的块
for(int i=pos[l]+1;i<=pos[r]-1;i++)
tag[i]+=c;
}
数列分块入门2：
操作：区间加法，询问区间内小于某个值 xxx 的元素个数
如果说我们每个数都去比较一遍，肯定是会t的，我们学分块主要还是学分块思想，我们对于每个块进行操作查询每个块中小于某个值 xxx 的元素个数，不就可以大大节省时间了吗？那由此可知为了更快获得小于某个数的个数，我们必须要求块内数据有序。
黄大神采用的是vector，开个二维vector<int>v[xxxx],利用vector的lower_bound操作。同时我们需要注意一点，在原数据有序的基础上进行加减，原数据次序并不会比打乱，所以修改包含的块直接修改，但是对于那些并不是在一整块中的数据进行修改时，原次序可能会被打乱，所以对于这一部分数据要进行重新排序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
using namespace std;
inline long long read(){
long long x = 0; long long f = 1; char c = getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
return x*f;
}
long long n;
long long m;
long long opt,l,r,c;
long long z[5211314];
long long pos[5211314];
long long tag[5211314];
vector<long long>v[1314];
void reset(long long x){
v[x].clear();//清空该块内的元素
//重新插入
for(long long i = (x-1)*m+1; i<=x*m; i++) v[x].push_back(z[i]);
// 重新排序
sort(v[x].begin(),v[x].end());
}
void modify(long long l,long long r,long long c){//修改函数
if(pos[l] == pos[r]){//在同一块内
for(long long i = l; i<=r; i++)
z[i] += c;
// 排序只是在vector中有序，因为是原数组修改，所以需要清空此块重新插入进行排序
reset(pos[l]);
}
else {
for(long long i = l; i<=pos[l]*m; i++)
z[i] += c;
// 排序只是在vector中有序，因为是原数组修改，所以需要清空此块重新插入进行排序
reset(pos[l]);
//对块进行标记时，区间加法并不会影响序列次序，所以只需要标记块
for(long long i = pos[l]+1; i<=pos[r]-1; i++)
tag[i] += c;
for(long long i = (pos[r]-1)*m+1; i<=r; i++)
z[i] += c;
// 排序只是在vector中有序，因为是原数组修改，所以需要清空此块重新插入进行排序
reset(pos[r]);
}
}
long long query(long long l,long long r,long long f){
long long ans = 0;
if( pos[l] == pos[r]){
for(long long i = l; i<=r; i++)
if(z[i] + tag[pos[i]] < f)
ans++;
return ans;
}
else {
for(long long i = l; i<=pos[l]*m; i++)
if(z[i] + tag[pos[i]]< f)
ans++;
for(long long i = pos[l]+1; i<=pos[r]-1;i++){
long long t = f - tag[i];
//lowe_bound返回第一个大于或等于t的位置，减去begin得到区间内元素个数
ans += lower_bound(v[i].begin(),v[i].end(),t) - v[i].begin();
}
for(long long i = (pos[r]-1)*m+1; i<=r; i++)
if(z[i] +tag[pos[i]] < f)
ans++;
}
return ans;
}
int main(){
n = read();
m = sqrt(n);
//预处理每个点所在的快
for(long long i = 1; i<=n; i++) pos[i] = (i-1)/m+1;
for(long long i = 1; i<=n; i++) {
z[i] = read();
//将数据z[i]存入所在的块pos[i]
v[pos[i]].push_back(z[i]);
}
//利用sort把每个块内的数据排好序 begin和end 代表所要排序的范围即整个v[i][~]‘’
for(long long i = 1; i<=pos[n]; i++)sort(v[i].begin(),v[i].end());
for(long long i = 1; i<=n; i++){
opt = read();
if(opt == 0){
l = read();
r = read();
c = read();
modify(l,r,c);
}
if(opt == 1){
l = read();
r = read();
c = read();
printf("%lld\n",query(l,r,c*c));
}
}
return 0;
}
数列分块入门3：
操作：涉及区间加法，询问区间内小于某个值 xxx 的前驱（比其小的最大元素）
这个题让我相当难受，，，hzw写的用set来实现，而我感觉用vector也能实现，又鉴于我set并不了解，所以努力实现vector版本的却无奈于实力有限，在打算放弃的时候恰巧翻到一篇vector实现的博客，所以就按照那份代码改，最后还是没改出来，wa了一页多，唯一的ac是我为了验证这份代码的正确性，还是等什么时候改出来再发吧，，，其实就是和二差不多一样的，不知道哪里错了，就是改不出来，头疼
数列分块入门4：
操作：区间加法，区间求和
操作还是不完整的块暴力，完整的标记区间，不过需要预处理出每个块的和。
修改时，修改每个点或块的同时，需要修改每个块的和
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
inline int read(){
int x = 0; int f = 1; char c = getchar();
while(c<'0'||c>'9'){
if(c == '-')f=-f;
c=getchar();
}
while(c<='9'&&c>='0'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
long long n;
long long m;
const int maxn = 5211314;
long long z[maxn];//数组不能随便拿long long定义我还不知道为什么
long long pos[maxn];//刚刚做题遇到两次long long 定义MLE的情况
long long tag[maxn];//只是两天前做的就没改
long long sum[maxn];
long long opt,l,r,c;
long long ans;
void modify(long long l,long long r,long long v){
for(int i = l; i<=min(pos[l]*m,r); i++) {
z[i] += v;
sum[pos[i]] += v;
}
if(pos[l] != pos[r]){
int t = pos[r];
for(int i = (pos[r]-1)*m+1; i<=r;i++){
z[i] += v;
sum[t] += v;
}
}
for(int i = pos[l]+1; i<=pos[r]-1; i++){
tag[i] += v;
sum[i] += v*m;
}
}
long long query(long long l,long long r){
int h = pos[l];
for(int i = l; i<=min(pos[l]*m,r); i++){
ans += z[i] + tag[h];
}
if(pos[l] != pos[r]){
int t = pos[r];
for(int i = (pos[r]-1)*m+1; i<=r; i++){
ans += z[i]+tag[t];
}
}
for(int i = pos[l]+1; i<=pos[r]-1; i++){
ans += sum[i];
}
return ans;
}
int main(){
n = read();
m = sqrt(n);
for(int i = 1; i<=n; i++){
z[i] = read();
pos[i] = (i-1)/m+1;
sum[pos[i]] += z[i];
}
for(int i = 1; i<=n; i++){
opt = read();
l = read();
r = read();
c = read();
if(opt == 0)modify(l,r,c);
else printf("%lld\n",query(l,r)%(c+1));
ans = 0;//每次计算完需要重新赋初值
}
return 0;
}
数列分块入门5：
操作区间开方，区间求和
九个题当中除了第九题留给了莫队去解决，这是唯一一道没有写的题，区间开方？搞不明白，，，我太弱了
数列分块入门6：
操作：单点插入，单点询问
在loj上，这九道题中这道题的通过率仅次于第一道题，但这道题挺重要，我感觉难度上要比前几道题大一点，这道题由于插入的存在原分好的块内数据就会发生改变，而且块越来越大十分影响效率，所以需要重新分块。
//我代码还没理解透，以后再放吧。。。
数列分块入门7：
**操作：区间乘法，区间加法，单点询问****
非常经典的操作，在luogu上 线段树2和本题完全相同，还有和[AHOI2009]维护序列也是一样的，可是我一直调不出来，直接导致心态爆炸，还是太弱了。
数列分块入门8：
操作：操作涉及区间询问等于一个数 ccc 的元素，并将这个区间的所有元素改为 ccc
我的想法是和2差不很多，在每个块内使用lower_bound进行查找ccc元素，修改时使用懒标记，对于左右两个端点，暴力查找，然后实现所在块内的懒标记，后直接修改值。
可是和7一样，他们一起让我心态爆炸，，，
数列分块入门8：
操作：查询区间最小众数
这其实是莫队的题吧，用分块的话，基于桶排，每出现一个数下标为此数的数组++。同时记录数组最大值和下标即众数，每次进行比较，就能得出答案。不过，我还是感觉使用莫队，可以更快的得出答案，毕竟莫队不需要像分块重新去查找
