这是一个没咕多久但还是咕咕咕了的分块学习笔记……
先从一个问题引入吧：
给一个序列，支持求区间和
我：前缀和吧
还要支持区间修改（区间加一个数）
我：线段树可以
还要支持求区间小于k的数的个数，且每次询问的k都不一定相同
我：太难了/dk
另：卡平衡树
……
分块就可以解决这个问题/cy。分块，可以说是一个优雅的暴力。顾名思义，分块，就是把一个序列分成几个块来维护。
我们把一个长度为(n)的序列分成(sqrt{n})块，每块有(sqrt{n})个元素，多余的部分再分一块。对于每一块可以维护整体的信息。
接下来来看上面的几种操作怎么维护。
求区间和
对于一个区间，我们可以把他分成：左碎块，中间的整块，右碎块。
对于中间的整块，我们可以直接求。而左碎块和右碎块，也就是左右不满一块的部分，我们可以暴力求。因为一块最大(sqrt{n})个元素，所以枚举一遍还是很快的。
区间修改
这里，首先我们绝对不可能一个个枚举修改的。那怎么办呢？我们可以像线段树一样，维护一个标记。(f_i)表示第(i)个块里的每个元素都要加上(f_i)，那整块就要加上(sqrt{n} imes f_i)。这是对于整块的。
那么对于左碎块和右碎块呢？自然也是直接枚举啊。枚举谁不会， 在枚举过程中，别忘了维护区间整块的大小哦！
求区间内(le k)的数的个数
这里，我们可以同时维护另一个序列，这个序列中，每个块都是有序的，可以发现有序的块也可以同时实现上面的操作，然后在查询时，只要对每个块二分即可。
对于上面给出的那个题，有一个类似的就是 [Ynoi2017]由乃打扑克，以及 题解
接下来看一道模板题：P2357 守墓人
这里，减(k)其实可以看做加(-k)，而这个求主墓的风水其实是迷人眼球的，根本没有什么特殊的用处，当普通的求就好了。
code：
#include<cmath>
#include<cstdio>
#define ll long long
using namespace std;
int n,m;
ll a[200005];//初始序列
int sq,q[200005];//sq=sqrt(n)，qi表示i所在的块的编号
ll res[200005],f[200005];//resi表示第i个块的大小（指区间和），fi表示第i个块的标记
int min(int x,int y){return x<y?x:y;}
void change(int l,int r,ll k)//区间修改
{
for(int i=l;i<=min(q[l]*sq,r);i++)//这里的min是特判一下只有一块不到的情况，暴力做掉左边的块，管他碎不碎
{
a[i]+=k;//注意这里单点也要改哦！
res[q[i]]+=k;
}
if(q[l]!=q[r])//不止一个块，那么把右边的块也做掉
for(int i=(q[r]-1)*sq+1;i<=r;i++)//暴力做右边的块，管他碎不碎
{
a[i]+=k;//注意这里单点也要改
res[q[i]]+=k;
}
for(int i=q[l]+1;i<q[r];i++)//做整块的
{
f[i]+=k;//整块的就直接加到标记上就好
res[i]+=k*sq;//一块是sq个元素，所以加k*sq。注意序列中最右边的块可能不满sq个，但由于上面已经把操作区间内的右边的块做掉了，所以不会到整块里来算
//注意fi只是对单点的效果，对于整块fi是没用的
}
return ;
}
ll query(int l,int r)
{
ll sum=0;
for(int i=l;i<=min(q[l]*sq,r);i++) sum+=a[i]+f[q[i]];//做左块
if(q[l]!=q[r])
for(int i=(q[r]-1)*sq+1;i<=r;i++) sum+=a[i]+f[q[i]];//右块
for(int i=q[l]+1;i<q[r];i++) sum+=res[i];//整块
//上面说了fi只是对单点的标记，所以算整块的时候不要把fi也加进去哦！
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
sq=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
q[i]=(i-1)/sq+1;
res[q[i]]+=a[i];
//读入并初始化
}
for(int i=1;i<=m;i++)
{
int opt;
scanf("%d",&opt);
if(opt<=3)//前三个都是区间修改
{
ll k;
if(opt==1)
{
int l,r;
scanf("%d%d%lld",&l,&r,&k);
change(l,r,k);//区间修改
}
else
{
scanf("%lld",&k);
change(1,1,opt==2?k:-k);//单点修改，不过和区间修改没什么差
}
}
else
{
if(opt==4)//区间查询
{
int l,r;
scanf("%d%d",&l,&r);
printf("%lld
",query(l,r));
}
else printf("%lld
",a[1]+f[1]);//这里只要查询一个点就好了。注意f1表示第1个块而不是第1个数，不要以为a1和f1的下标都是1就意义一样！
}
}
return 0;
}