在信息学竞赛中,常常会遇到一些区间修改或区间查询的题目,如果直接敲暴力的话,时间复杂度是 O ( n m ) O(nm) O(nm) 可能会超时,如果写树状数组或线段树的话,又有一点复杂,不易理解,那么这时候就要请出我们今天的主角——分块
分块简述
分块分块,顾名思义,就是把一个区间分成几小块,然后对于每个块进行单独的处理。它的核心思想是 将一个大规模的输入划分成更小的“块”,然后针对每一块单独处理。这种方法可以显著降低时间复杂度和空间复杂度,尤其适合 处理静态数据的查询问题。例如,区间求和、最值查询等。
分块的优缺点
分块的优点在于:
- 局部化处理:只需要处理相关的块,而无需遍历整个数据集。
- 灵活性:通过调整块大小,可以在时间复杂度和空间复杂度之间找到平衡。
- 降低查询和更新的复杂度:通常可以将复杂度降低到 O ( n ) O(\sqrt{n}) O(n)或 O ( log n ) O(\log n) O(logn)级别。
分块的缺点在于:
- 容易被卡时间:当我们遇到要进行添加元素的题目的时候,就会被卡时间复杂度,如果出题人非常的毒瘤,他可能会往一个块里使劲加,从而是这个块非常的大(但是有办法解决)
- 时间复杂度不够低:因为线段树是 O ( n log n ) O(n \log n) O(nlogn) 级的时间复杂度,所以有些题目可能不支持 O ( n n ) O(n \sqrt n) O(nn) 算法通过,这就非常的尴尬。
分块算法的具体实现步骤
下面我们通过一个简单的例子来展示分块的实现过程:假设我们有一个数组,需要多次进行区间求和查询。
1. 确定块的大小
假设数组有 n n n 个元素。通常,为了优化时间复杂度,我们把块大小设为 B = n B = \sqrt{n} B=n,这样会得到 n B ≈ n \frac{n}{B} \approx \sqrt{n} Bn≈n 个块。(证明见1)
- 如果块的大小太小,块的数量会很多,可能导致整体复杂度增加。
- 如果块的大小太大,单个块的查询效率会下降。
示范代码
k=sqrt(n);
2. 构建块
- 将数组划分成多个块,例如第一个块是数组的前 (B) 个元素,第二个块是接下来的 (B) 个元素,依此类推。
- 对每一个块进行预处理,存储它们的总和或其他需要的信息。这样,在进行查询时,我们可以直接访问块的预处理结果。
举个例子,假设我们有一个数组 arr
:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],我们把它分成 3 个块,每块大小为 3。
示范代码
for (int i=1;i<=n;i++){cin>>a[i];pos[i]=(i-1)/k+1;//存储当前元素应该在第几号块
}
3. 预处理块
对每个块计算并保存其总和。例如,以上数组分块后的块求和是:
- 块1(包含1, 2, 3):总和为 6
- 块2(包含4, 5, 6):总和为 15
- 块3(包含7, 8, 9):总和为 24
这些块的总和我们存储在一个新数组 block_sum
中,方便后续快速访问。
for (int i=1;i<=n;i++){block_sum[pos[i]]+=a[i];
}
4. 实现查询操作
假设我们要查询某个区间内元素的和,例如查询 arr[2]
到 arr[8]
的和,我们可以按照以下步骤进行:
- 先处理起始和结束块内部的部分(因为区间可能不是完整的块)。
- 直接使用块的预处理结果,跳过中间完整的块。对于中间完整的块,可以直接使用
block_sum
中的值,不用遍历。
例如,查询 arr[2]
到 arr[8]
,我们可以分三部分处理:
- 第一个块处理
arr[2]
到arr[2]
,即3。 - 中间的完整块(块2)总和直接用
block_sum
中的值:15。 - 最后一个块处理
arr[6]
到arr[8]
,即7 + 8 + 9 = 24
。
这样,总和就是 3 + 15 + 24 = 42
,我们没有遍历所有元素,而是用了预处理好的块和结果。
void update1(){int ans=0;for (int i=l;i<=min(r,pos[l]*k);i++){//处理两侧的零散空间ans+=a[i];}if (pos[l]==pos[r])return;for (int i=(pos[r]-1)*k+1;i<=r;i++){ans+=a[i];}for (int i=pos[l]+1;i<=pos[r]-1;i++){ans+=block_sum[i];}cout<<ans<<endl;return;
}
5. 更新操作(可选)
如果需要动态更新数据,例如改变数组中的某个值,我们也可以通过分块来处理。
- 更新某个元素时,我们更新所在块的总和即可,而不需要重新计算所有块。
- 例如将
arr[3]
改成10,那么对应块1的和就要相应调整。
void update1(){for (int i=l;i<=min(r,pos[l]*k);i++){a[i]+=c;}if (pos[l]==pos[r])return;for (int i=(pos[r]-1)*k+1;i<=r;i++){a[i]+=c;}for (int i=pos[l]+1;i<=pos[r]-1;i++){plu[i]+=c;plu[i]%=MOD;}return;
}
分块算法的时间复杂度分析
- 查询复杂度:由于分块后的查询只需要遍历开头和结尾的部分块,再加上中间的少数块总和,时间复杂度通常是 O ( n ) O(\sqrt{n}) O(n)。
- 更新复杂度:每次更新时只需要修改一个块的总和,复杂度也是 O ( n ) O(\sqrt{n}) O(n) 。
小结
分块算法通过 划分数据、预处理块信息、优化查询效率 等手段,适用于大数据量下的区间查询类问题。
这种思想也延展到了 莫队算法 和 线段树 等高级数据结构中,为复杂查询问题提供了高效解决方案。
上例题(基础的我们就不看了,上点有强度的)
例题
例1
打眼一瞧,懵了,啥玩意这是?和我们刚刚讲的是一个玩意吗?
不慌,我们慢慢来分析。
首先操作一我们是会的吧,上面有模板,接下来就看操作二。
如果我们每次都是去暴力枚举的话,时间复杂度直接到达 O ( n m ) O(nm) O(nm) ,承受不住。那怎么办?用二分,如果我对每个块都排一遍序的话,是不是就可以用二分来找到 c 2 c^2 c2 的位置了?这是有人就会问了,尽管我们在对整个块进行操作的时候,不会有错,但是在对两侧零散的块进行操作的时候呢?这不简单?直接将左右两侧零散的块给重新排个序不就行了?
这样的时间复杂度就是 O ( n n log n ) O(n \sqrt{n} \log {\sqrt n}) O(nnlogn)
#include<bits/stdc++.h>
using namespace std;
const int INF=50000+10;
int a[INF],cla[INF],tot[INF];
int k,n;
vector<int> t[250];void resort(int x){t[x].clear();for (int j=(x-1)*k+1;j<=min(n,x*k);j++){t[x].push_back(a[j]);}sort(t[x].begin(),t[x].end());return;
}
void imp(int l,int r,int c){ for (int i=l;i<=min(r,cla[l]*k);i++){a[i]+=c;}resort(cla[l]);if (cla[l]==cla[r])return;for (int i=r;i>=(cla[r]-1)*k+1;i--){a[i]+=c;}resort(cla[r]);for (int i=cla[l]+1;i<cla[r];i++){tot[i]+=c;}return;
}void pro(int l,int r,int c){int ans=0;for (int i=l;i<=min(r,cla[l]*k);i++){if (a[i]+tot[cla[l]]<c*c)ans++;}if (cla[l]==cla[r]){cout<<ans<<endl;return;}for (int i=r;i>=(cla[r]-1)*k+1;i--){if (a[i]+tot[cla[r]]<c*c)ans++;}for (int i=cla[l]+1;i<cla[r];i++){int place=lower_bound(t[i].begin(),t[i].end(),c*c-tot[i])-t[i].begin();ans+=place;}cout<<ans<<endl;return;
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;k=sqrt(n);for (int i=1;i<=n;i++){cin>>a[i];cla[i]=(i-1)/k+1;t[cla[i]].push_back(a[i]);}for (int i=1;i<=cla[n];i++){sort(t[i].begin(),t[i].end());}for (int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c;if (opt==0){imp(l,r,c);}else {pro(l,r,c);}}return 0;
}
设每个块的大小为 B B B 个元素,那么我们总共有 n B \frac{n}{B} Bn 个块如果查询一个随机区间 [ L , R ] [L,R] [L,R],则需要遍历 起始和结束的两个部分块,并直接使用 中间完整块 的预处理结果。由此可见此,查询的时间复杂度可以近似分解为以下两部分:遍历两个不完整块中的元素,复杂度为 O ( B ) O(B) O(B) 查询中间完整块,复杂度为 O ( n B ) O(\frac{n}{B}) O(Bn)。
所以,查询的总时间复杂度为: O ( B ) + O ( n B ) O(B)+O(\frac{n}{B}) O(B)+O(Bn)
为了找到最优的块大小 B B B ,我们可以将 O ( B ) + O ( n B ) O(B)+O(\frac{n}{B}) O(B)+O(Bn) 视为一个函数,并对其求导来最小化它,
令 T ( B ) = B + n B T(B)=B+\frac{n}{B} T(B)=B+Bn ,对 T ( B ) T(B) T(B) 关于 B B B 求导得 T ′ ( B ) T^′(B) T′(B) 并设为0。
则有 T ′ ( B ) = 1 − n B 2 = 0 T^′ (B)=1−\frac{n}{B^2}=0 T′(B)=1−B2n=0
解这个方程的 B = n B=\sqrt n B=n ↩︎