【算法每日一练]-分块（保姆级教程 篇1）POJ3648

插讲一下分块

        

        

题目：（POJ 3648） 一个简单的整数问题

        

        

前缀和往往用于静态的不会修改的区间和。遇到经常修改的区间问题，就要用分块或线段树来维护了。

分块算法是优化后的暴力，分块算法有时可以维护一些线段树维护不了的东西，虽然效率一般不如线段树，但是比线段树更易上手。

         

         

分块算法分3步骤：

        

1，预处理块：处理块长（往往是根号n），每块的左右下标L[], R[]，每块的区间和suf[]，每个元素所属的块号pos[]

        

2，区间修改：对于完整的块仅修改懒标记，不完整的就暴力修改a[]和suf[]

        

3，区间查询 ：对于完整的块直接利用懒和suf，不完整的就暴力

        

#include <bits/stdc++.h>//POJ3648
using namespace std;
const int N=100010;
typedef long long ll;
ll a[N],suf[N],add[N];
int L[N],R[N],pos[N];
int n,m,t,l,r,d;
char op[3];
//分块预处理：（我们处理下标都是从1开始）
void build(){//处理t块长，L[]R[]每块的左右下标，pos[]每个下标的所属块号，suf[]每块的和t=sqrt(n*1.0);int num=n/t;if(n%t) num++;for(int i=1;i<=num;i++){L[i]=(i-1)*t+1;R[i]=i*t;}R[num]=n;//更改最后一块的右下标for(int i=1;i<=num;i++){for(int j=L[i];j<=R[i];j++){pos[j]=i;suf[i]+=a[j];}}
}
//区间修改
void change (int l,int r,ll d){//修改add[]懒标，a[]和suf[]int p=pos[l],q=pos[r];if(p==q){//如果在同一块就暴力修改a[]和suf[]for(int i=l;i<=r;i++) a[i]+=d;suf[p]+=d*(r-l+1);}else{//完整的块仅修改懒标，不完整就暴力for(int i=p+1;i<=q-1;i++) add[i]+=d;for(int i=l;i<=R[p];i++) a[i]+=d;suf[p]+=d*(R[p]-l+1);for(int i=L[q];i<=r;i++) a[i]+=d;suf[q]+=d*(r-L[q]+1);}
}ll query(int l,int r){int p=pos[l],q=pos[r];ll ans=0;if(p==q){//同一块就暴力for(int i=l;i<=r;i++) ans+=a[i];ans+=add[p]*(r-l+1);}else{//完整就suf+add，不完整就暴力for(int i=p+1;i<=q-1;i++) ans+=suf[i]+add[i]*(R[i]-L[i]+1);for(int i=l;i<=R[p];i++) ans+=a[i];for(int i=L[q];i<=r;i++) ans+=a[i];ans+=add[q]*(r-L[q]+1);}return ans;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}build();for(int i=1;i<=m;i++){scanf("%s %d %d",op,&l,&r);if(op[0]=='C'){scanf("%d",&d);change(l,r,d);}else{printf("%lld\n",query(l,r));}}
}