【算法】分块

分块感觉也没必要讲多了，人家 hzwer 讲得多好……%%hzw%%orz。
传送门

再贴个我写的分块区间增减、区间求和。
题目：洛谷 P3372【模板】线段树 1 传送门

思想：把大小为 n 的数组分成√n 块，每块含√n 个元素。（因为把大小为 n 的数组分成√n 块是最好的分法，具体怎么证我不知道～=￣ω￣=）然后对于每次修改区间 [l,r]，先单独处理 l~l 所在的块的末尾元素和 r 所在的块的开始元素~r，最坏情况复杂度使 2×√n，然后中间的都是整块整块的块了，所以我们把每个块都做上懒惰标记就行了。（懒惰标记不知道的去看我的那篇线段树入门！）中间最多有√n 块，所以整个操作的复杂度不会超过 3×√n。查询也是一个套路，只不过要每次加上懒惰标记值。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,sqn,bl[100005];
ll v[100005],d[405],atag[405],x;
void update(int l,int r,ll k)
{
    int lim=min(bl[l]*sqn,r);
    for(int i=l;i<=lim;i++)v[i]+=k,d[bl[i]]+=k;
    if(bl[l]!=bl[r])for(int i=(bl[r]-1)*sqn+1;i<=r;i++)v[i]+=k,d[bl[i]]+=k;
    for(int i=bl[l]+1;i<bl[r];i++)atag[i]+=k;
}
ll getsum(int l,int r)
{
    int lim=min(bl[l]*sqn,r);ll sum=0;
    for(int i=l;i<=lim;i++)sum+=v[i]+atag[bl[i]];
    if(bl[l]!=bl[r])for(int i=(bl[r]-1)*sqn+1;i<=r;i++)sum+=v[i]+atag[bl[i]];
    for(int i=bl[l]+1;i<bl[r];i++)sum+=d[i]+sqn*atag[i];
    return sum;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m,sqn=(int)(sqrt(n));
    for(int i=1;i<=n;i++)cin>>v[i],bl[i]=(i-1)/sqn+1,d[bl[i]]+=v[i];
    for(int i=1,a,b,c;i<=m;i++)
    {
        cin>>a>>b>>c;
        if(a==1)cin>>x,update(b,c,x);
        else cout<<getsum(b,c)<<endl;
    }
    return 0;
}