分块
优雅的暴力。
分块的思想是通过划分和预处理来达到时间复杂度的平衡。
分块后任取一区间，中间会包含整块和零散块。一般对零散块暴力处理，整块通过预处理的信息计算。
常见的分块有数列分块，值域分块，数论分块等，运用于不同的情境。
分块的复杂度一般劣于线段树等 \(log\) 数据结构，但是运用范围广。
分块的实现
总体来说 : 划分 -> 处理必要信息 -> 操作
以 洛谷P3374 【模板】树状数组 1 为例
维护一个长度为 \(n\) 的数列 \(a\) ，共 \(m\) 次操作
1 x k将第 \(x\) 个数加上 \(k\)
2 x y输出区间 \([x,y]\) 内每个数的和
\(1 \leq n,m \leq 5 \times 10^{5}\)
1.划分
可以用固定块长划分，也可以直接 \(\sqrt{n}\) 为块长。后文无特殊说明均使用后者。
此时数列被划分成 \(\sqrt{n}\) 块，需要记录每一块的左右端点，以及每个元素所属块。
注意可能最后一块是不完整的，块长不一定为 \(\sqrt{n}\) 。
2.处理必要信息
因为要求和，所以我们预处理出每一块的元素总和。
用 \(sum_{i}\) 表示第 \(i\) 块的元素和。
3.操作
两种，一个修改一个查询。
先来看修改，将第 \(x\) 个数加上 \(k\) ，同时也要将其所在块的元素和加上 \(k\) 。
再看查询，设 \(x\) 在第 \(p\) 块，\(y\) 在第 \(q\) 块。
\(1. \ p = q\)
表示 \(x\) 和 \(y\) 在同一块内，\([x,y]\) 中元素个数不超过 \(\sqrt{n}\) ，可以暴力统计。
\(2. \ p \neq q\)
此时 \([x,y]\) 由如下三部分组成：
-
左边的散块 \(p\)
这部分内元素个数不超过 \(\sqrt{n}\) ，直接统计求和。 -
中间的完整块 \(p+1 \sim q-1\)
完整块的个数不超过 \(\sqrt{n}\) 个，枚举每个块并将其 \(sum\) 相加即可。
注意当 \(p + 1 = q\) 时中间是没有完整块的，但是并不影响。 -
右边的散块 \(q\)
这部分内元素个数不超过 \(\sqrt{n}\) ，直接统计求和。
这里散块有可能是完整的一块，不过不影响。
#include<cmath>
#include<cstdio>
const int M=5e5+10,len=800;
int n,m;
int L[len],R[len],bel[M];
int a[M],sum[len];
void build(){
int size=sqrt(n);//块长
for(int i=1;i<=n;i++) bel[i]=(i-1)/size+1;//计算元素所在块
for(int i=1;i<=bel[n];i++) L[i]=(i-1)*size+1,R[i]=i*size;//每一块的左右端点
R[bel[n]]=n;//最后一块的右端点为n
for(int i=1;i<=bel[n];i++)//枚举每一块
for(int j=L[i];j<=R[i];j++) sum[i]+=a[j];
}
void modify(int x,int k){//修改
a[x]+=k;
sum[bel[x]]+=k;//所在块的和也要修改
}
int query(int l,int r){
int p=bel[l],q=bel[r],ans=0;
if(p==q){
for(int i=l;i<=r;i++) ans+=a[i];
//两端点在同一块内，直接暴力统计。
return ans;
}else{
for(int i=l;i<=R[p];i++) ans+=a[i];//左边的散块
for(int i=L[q];i<=r;i++) ans+=a[i];//右边的散块
for(int i=p+1;i<=q-1;i++) ans+=sum[i];//中间的整块
return ans;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build();
for(int i=1,opt,x,y;i<=m;i++){
scanf("%d%d%d",&opt,&x,&y);
if(opt==1) modify(x,y);
if(opt==2) printf("%d\n",query(x,y));
}
return 0;
}
懒标记思想
和线段树的懒标记差不多。
洛谷P3372 【模板】线段树 1 / Loj #6280. 数列分块入门 4
维护一个长度为 \(n\) 的数列 \(a\) ，共 \(m\) 次操作
1 x y k将区间 \([l,r]\) 的每个元素加上 \(k\)
2 x y询问区间 \([l,r]\) 的元素和
\(1 \leq n,m \leq 10^{5}\)
上一题的升级版，要引入懒标记思想。
对于操作 \(1\) 不可能一个个加，所以利用分块思想。
设 \(l\) 在第 \(p\) 块，\(r\) 在第 \(q\) 块。
\(1. \ p = q\)
直接暴力操作即可。
\(2. \ p \neq q\)
这个时候 \([l,r]\) 由三部分组成:
-
左边的散块 \(p\)
暴力操作，最多 \(\sqrt{n}\) 个元素。 -
中间的完整块 \(p+1 \sim q-1\)
对其打上懒标记 \(lazy\) ，表示这一块整体还剩 \(lazy\) 没有加上去。
lazy[x] += k -
右边的散块 \(q\)
暴力操作，最多 \(\sqrt{n}\) 个元素。
查询和上一题差不多，但是要记得加上 \(lazy\) 的贡献。
这题的懒标记下传不下传都行。但是多数分块题是要下传的，所以写了下传的版本。下传时注意是散块的下传。
记得开 long long
void pushdown(int p){
for(int i=L[p];i<=R[p];i++) a[i]+=lazy[p];
sum[p]+=lazy[p]*(R[p]-L[p]+1);//维护块内和
lazy[p]=0;//清空懒标记
}
void modify(int l,int r,int k){
int p=bel[l],q=bel[r];
if(p==q){
pushdown(p);//散块下传懒标记
for(int i=l;i<=r;i++) a[i]+=k;
sum[p]+=(r-l+1)*k;
}else{
pushdown(p),pushdown(q);//处理左右散块
for(int i=l;i<=R[p];i++) a[i]+=k;
for(int i=L[q];i<=r;i++) a[i]+=k;
sum[p]+=(R[p]-l+1)*k;
sum[q]+=(r-L[q]+1)*k;
for(int i=p+1;i<=q-1;i++) lazy[i]+=k;//整块打上懒标记
}
}
int query(int l,int r){
int p=bel[l],q=bel[r],ans=0;
if(p==q){
pushdown(p);
for(int i=l;i<=r;i++) ans+=a[i];
}else{
pushdown(p),pushdown(q);
for(int i=l;i<=R[p];i++) ans+=a[i];//左散块的和
for(int i=L[q];i<=r;i++) ans+=a[i];//右散块的和
for(int i=p+1;i<=q-1;i++) ans+=sum[i]+lazy[i]*(R[i]-L[i]+1);
}
return ans;
}
洛谷 P2801 教主的魔法 / Loj #6278. 数列分块入门 2
维护一个长度为 \(n\) 的数列，共 \(q\) 次操作:
M l r w区间 \([l,r]\) 所有元素加上 \(w\)
A l r c询问区间 \([l,r]\) 有多少数大于等于 \(c\)
\(1 \leq n \leq 10^{6}\) , \(1 \leq q \leq 3000\)
区间加可以想到懒标记。问题是如何处理询问操作。
对于每一块我们可以维护一个新数组 \(d\) ，用于储存每一块元素的非降序排列。
如序列 5 4 / 3 2 / 1 ，块长为 \(2\) ，那么 \(d\) 数组为 4 5 / 2 3 / 1 。
设询问区间 \(l\) 在第 \(p\) 块，\(r\) 在第 \(q\) 块。
\(p = q\) 时直接暴力重构块，保证 \(d\) 内每块中元素单调不降。
\(p \neq q\) 时，注意到一整块的元素都加上值 \(w\) ，块内相对大小不变。所以直接打懒标记即可。
而散块中只有一部分加上了 \(w\) ，所以块内相对大小可能改变了。但是散块中最多有 \(\sqrt{n}\) 个元素，所以直接暴力重构即可。
重构的时候注意顺序，先下传懒标记，然后再重构。
查询的时候在每块内二分查找即可。时间复杂度 \(O(n\sqrt{n}\log{n})\)
void build(){
len=sqrt(n);
for(int i=1;i<=n;i++) bel[i]=(i-1)/len+1;
for(int i=1;i<=bel[n];i++) L[i]=(i-1)*len+1,R[i]=i*len;
R[bel[n]]=n;
for(int i=1;i<=n;i++) d[i]=a[i];
for(int i=1;i<=bel[n];i++) sort(d+L[i],d+R[i]+1);
}
void restruct(int p){//暴力重构
for(int i=L[p];i<=R[p];i++) d[i]=a[i];
sort(d+L[p],d+R[p]+1);
}
void pushdown(int p){
for(int i=L[p];i<=R[p];i++) a[i]+=lazy[p],d[i]+=lazy[p];
lazy[p]=0;
}
void update(int l,int r,int w){
int p=bel[l],q=bel[r];
if(p==q){
pushdown(p);
for(int i=l;i<=r;i++) a[i]+=w;
restruct(p);
}else{
pushdown(p),pushdown(q);
for(int i=l;i<=R[p];i++) a[i]+=w;
for(int i=L[q];i<=r;i++) a[i]+=w;
restruct(p),restruct(q);
for(int i=p+1;i<=q-1;i++) lazy[i]+=w;
}
}
int query(int l,int r,int c){
//这里是统计比 c 小的元素个数
//最后用区间长度减去它就可以得到大于等于 c 的元素个数
int p=bel[l],q=bel[r],ans=0;
if(p==q){
pushdown(p);
for(int i=l;i<=r;i++) ans+=(a[i]<c);
}else{
pushdown(p),pushdown(q);
for(int i=l;i<=R[p];i++) ans+=(a[i]<c);
for(int i=L[q];i<=r;i++) ans+=(a[i]<c);
for(int i=p+1;i<=q-1;i++) ans+=(lower_bound(d+L[i],d+R[i]+1,c-lazy[i])-d-L[i]);
}
return r-l+1-ans;
}