分块——优雅的暴力

下面介绍一种暴力，当然呢这种暴力比一般快很多。
先说一下这个暴力的思路。对于一个长度为\(n\)的数组\(a\)，可以把数组\(a\)分成\(k\)块，其中每一块的长度为\(len\)，当然最后一行除外因为\(n\)可能不是\(k\)的倍数，最后一块的长度可以不是\(len\)。
那么就可以用这些块来维护数据。
那么对于一个区间\([l..r]\)可以分成两种情况：
\(1\).区间\([l..r]\)在同一个块里也就是：

这种情况下可以暴力枚举\(l\)到\(r\)即可。
\(2\).区间\([l..r]\)不在同一个块里也就是：、

这种情况下首先应该考虑中间整块的部分(图中\(3,4f\))，然后就是\(l\)和\(r\)中的残块也就是\(2\)和\(5\)中间的那一部分。

例题I 线段树1

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

11
8
20

现在这一题是要支持区间求和，很显然用分块来维护区间和，那么可以用一个数组\(s\)表示当前块的最大和。
对于每一次的询问仍旧分为两部分\(l\)和\(r\)在同一块里和\(l\)和\(r\)不在同一块里。
那么代码就是:

int query(int l,int r){
    int sid=id[l],eid=id[r];//表示开始块编号和结束块编号
    if(sid==eid){//l,r在同一块里
        int sum=0;
        for(int i=l;i<=r;i++)sum+=a[i]+b[sid];//这里的a是原数组,b是每一块的懒标记
        return sum;
    }
    int sum=0;
    for(int i=l;id[i]==sid;i++)sum+=a[i]+b[sid];//l所对应的残块
    for(int i=sid+1;i<eid;i++)sum+=s[i];//l,r中间的真快,s是每一块的和
    for(int i=r;id[i]==eid;i--)sum+=a[i]+b[eid];//r所对应的残块
    return sum;
}

修改的方法和询问是一样的

void add(int l,int r,int x){
	int sid=id[l],eid=id[r];
	if(sid==eid){
		for(int i = l;i <= r;i ++ )s[sid] += x，a[i] += x;
		return;
	}
	for(int i = l;id[i] == id[l];i ++ ) s[id[l]] +=x,a[i] +=x;
	for(int i = sid + 1;i < eid;i ++ )s[i] += len * x,b[i] += x;
	for(int i = r;id[i] == id[r];i -- ) s[id[r]] +=x, a[i] += x;
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int a[N],b[N],s[N];
int id[N];
int n,m,len;
int query(int l,int r){
    int sid=id[l],eid=id[r];
    if(sid==eid){
        int sum=0;
        for(int i=l;i<=r;i++)sum+=a[i]+b[sid];
        return sum;
    }
    int sum=0;
    for(int i=l;id[i]==sid;i++)sum+=a[i]+b[sid];
    for(int i=sid+1;i<eid;i++)sum+=s[i];
    for(int i=r;id[i]==eid;i--)sum+=a[i]+b[eid];
    return sum;
}
void add(int l,int r,int x){
    int sid=id[l],eid=id[r];
    if(sid==eid){
        for(int i = l;i <= r;i ++ ){
            s[sid] += x;
            a[i] += x;
        }
        return;
    }
    for(int i = l;id[i] == id[l];i ++ ) s[id[l]] +=x,a[i] +=x;
    for(int i = r;id[i] == id[r];i -- ) s[id[r]] +=x, a[i] += x;
    for(int i = sid + 1;i < eid;i ++ ){
        s[i] += len * x;
        b[i] += x;
    }
}
signed main(){
    cin>>n>>m;
    len=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        int cnt=(i-1)/len+1;
        id[i]=cnt;
        s[cnt]+=a[i];
    }
    while(m--){
        int ops,l,r,c;cin>>ops>>l>>r;
        if(ops==1)cin>>c,add(l,r,c);
        else cout<<query(l,r)<<'\n';
    }
    return 0;
}

例题II

5 4
4 5
2 4
2 5
2 2

1
4
3
3

2 1
2 1

1

6 7
1 4
3 5
2 3
3 3
3 6
2 1
5 1

5
6
7
7
10
11
8