分块

分块是一种好想、好写、应用范围广的数据结构，其时间复杂度为 ，空间复杂度一般不超过 。对于处理单点修改，区间修改，单点查询，区间查询，以及各种奇怪应用场景都能发挥作用，被称为优雅的暴力。

例题 洛谷P3372 区间修改，区间查询

分块大小为 ，然后对于每块设置一个懒标记，修改的时候若整块就修改懒标记，零散的就下传懒标记并单点修改，具体看代码吧。

#include<bits/stdc++.h>
using namespace std;
#define rep(n) for(int i=0;i<n;i++)
typedef long long ll;
const int N=1e5+9;
ll a[N];
ll sum[1000];
ll lazy[1000];
void init(int n,int sz)
{
    rep(n)sum[i/sz]+=a[i];
}
void pushdown(int t,int sz)
{
    rep(sz)a[t*sz+i]+=lazy[t],sum[t]+=lazy[t];
    lazy[t]=0;
}
void add(int x,int y,ll k,int sz)
{
    int l=x/sz,r=y/sz;
    if(x%sz){pushdown(l,sz);for(int i=x%sz;i<sz;i++)a[l*sz+i]+=k,sum[l]+=k;l++;}
    if(y%sz!=sz-1){pushdown(r,sz);for(int i=0;i<=y%sz;i++)a[r*sz+i]+=k,sum[r]+=k;r--;}
    for(int i=l;i<=r;i++)lazy[i]+=k;
}
ll quiry(int x,int y,int sz)
{
    ll ans=0;
    int l=x/sz,r=y/sz;
    if(x%sz){pushdown(l,sz);for(int i=x%sz;i<sz;i++)ans+=a[l*sz+i];l++;}
    if(y%sz!=sz-1){pushdown(r,sz);for(int i=0;i<=y%sz;i++)ans+=a[r*sz+i];r--;}
    for(int i=l;i<=r;i++)ans+=lazy[i]*sz+sum[i];
    return ans;
}

int main()
{
    int n,m;cin>>n>>m;
    rep(n)cin>>a[i];
    int sz=sqrt(n);
    init(n,sz);
    rep(m)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int x,y;ll k;cin>>x>>y>>k;
            add(x-1,y-1,k,sz);
        }
        if(t==2)
        {
            int x,y;cin>>x>>y;
            cout<<quiry(x-1,y-1,sz)<<endl;
        }
    }
    return 0;
}
// 用分块过了线段树的题
// 教训：定义变量名尽量意思明确一些
// 否则改代码会非常难受
// 一定要分清是对元素操作还是对块操作，写错了真的很难检查出来