“优雅的暴力”——分块
分块是一种暴力的优化，虽然效率比线段树、树状数组等数据结构低的多 \((N+Q)\sqrt{N}\)，但是更加灵活。
分块的思想是把整个区间分成几个部分，对于要处理的区间包括两个部分 “整块”，和 区间边缘的“零散块”，
“零散块”直接暴力，“整块”进行整体操作即可。
听起来可能和线段树有点像,其实分块可以看成一颗只有三层的树，
区别在于分块可以处理一些区间之间没有结合律的（如众数）。
分块思路相对好想，重点在于如何把整个区间的操作转化为“整块”的操作。
例题
$\mathbb{code}$
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100005;
int n,m;
LL a[N],sum[400],add[400];
int L[400],R[400],bl[N],siz[400];
void bui()
{
int cnt=sqrt(n);
for(int i=1;i<=cnt;i++)
{
L[i]=n/cnt*(i-1)+1;
R[i]=n/cnt*i;
}
R[cnt]=n;
for(int i=1;i<=cnt;i++)
{
for(int j=L[i];j<=R[i];j++)
{
bl[j]=i; sum[i]+=a[j];
}
siz[i]=R[i]-L[i]+1;
}
}
void mdf(int l,int r,int v)
{
if(bl[l]==bl[r])
{
for(int i=l;i<=r;i++)
{
a[i]+=v; sum[bl[l]]+=v;
}
}
else
{
for(int i=l;i<=R[bl[l]];i++)
{
a[i]+=v; sum[bl[l]]+=v;
}
for(int i=L[bl[r]];i<=r;i++)
{
a[i]+=v; sum[bl[r]]+=v;
}
for(int i=bl[l]+1;i<bl[r];i++)
{
add[i]+=v;
}
}
}
LL que(int l,int r)
{
LL ans=0;
if(bl[l]==bl[r])
{
for(int i=l;i<=r;i++) ans+=a[i]+add[bl[l]];
}
else
{
for(int i=l;i<=R[bl[l]];i++) ans+=a[i]+add[bl[l]];
for(int i=L[bl[r]];i<=r;i++) ans+=a[i]+add[bl[r]];
for(int i=bl[l]+1;i<bl[r];i++) ans+=sum[i]+siz[i]*add[i];
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
bui();
for(int i=1;i<=m;i++)
{
string s; cin>>s;
if(s[0]=='C')
{
int l,r,v;
scanf("%d%d%d",&l,&r,&v);
mdf(l,r,v);
}
if(s[0]=='Q')
{
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",que(l,r));
}
}
return 0;
}