分块——最为优雅的暴力

在信息学竞赛中，常常会遇到一些区间修改或区间查询的题目，如果直接敲暴力的话，时间复杂度是 $O(nm)$ 可能会超时，如果写树状数组或线段树的话，又有一点复杂，不易理解，那么这时候就要请出我们今天的主角——分块

分块简述

分块分块，顾名思义，就是把一个区间分成几小块，然后对于每个块进行单独的处理。它的核心思想是 将一个大规模的输入划分成更小的“块”，然后针对每一块单独处理。这种方法可以显著降低时间复杂度和空间复杂度，尤其适合 处理静态数据的查询问题。例如，区间求和、最值查询等。

分块的优缺点

分块的优点在于：

1. 局部化处理：只需要处理相关的块，而无需遍历整个数据集。
2. 灵活性：通过调整块大小，可以在时间复杂度和空间复杂度之间找到平衡。
3. 降低查询和更新的复杂度：通常可以将复杂度降低到$O(\sqrt{n})$或$O(\log n)$级别。

分块的缺点在于：

1. 容易被卡时间：当我们遇到要进行添加元素的题目的时候，就会被卡时间复杂度，如果出题人非常的毒瘤，他可能会往一个块里使劲加，从而是这个块非常的大（但是有办法解决）
2. 时间复杂度不够低：因为线段树是 $O(n\log n)$ 级的时间复杂度，所以有些题目可能不支持 $O(n\sqrt{n})$ 算法通过，这就非常的尴尬。

分块算法的具体实现步骤

下面我们通过一个简单的例子来展示分块的实现过程：假设我们有一个数组，需要多次进行区间求和查询。

1. 确定块的大小

假设数组有 $n$ 个元素。通常，为了优化时间复杂度，我们把块大小设为 $B=\sqrt{n}$，这样会得到 $\frac{n}{B}\approx \sqrt{n}$ 个块。（证明见¹）

• 如果块的大小太小，块的数量会很多，可能导致整体复杂度增加。
• 如果块的大小太大，单个块的查询效率会下降。

示范代码

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] 的和，我们可以按照以下步骤进行：

1. 先处理起始和结束块内部的部分（因为区间可能不是完整的块）。
2. 直接使用块的预处理结果，跳过中间完整的块。对于中间完整的块，可以直接使用 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(\sqrt{n})$。
• 更新复杂度：每次更新时只需要修改一个块的总和，复杂度也是 $O(\sqrt{n})$ 。

小结

分块算法通过 划分数据、预处理块信息、优化查询效率 等手段，适用于大数据量下的区间查询类问题。
这种思想也延展到了 莫队算法 和 线段树 等高级数据结构中，为复杂查询问题提供了高效解决方案。

上例题（基础的我们就不看了，上点有强度的）

例题

例1

打眼一瞧，懵了，啥玩意这是？和我们刚刚讲的是一个玩意吗？
不慌，我们慢慢来分析。
首先操作一我们是会的吧，上面有模板，接下来就看操作二。
如果我们每次都是去暴力枚举的话，时间复杂度直接到达 $O(nm)$ ，承受不住。那怎么办？用二分，如果我对每个块都排一遍序的话，是不是就可以用二分来找到 $c^2$ 的位置了？这是有人就会问了，尽管我们在对整个块进行操作的时候，不会有错，但是在对两侧零散的块进行操作的时候呢？这不简单？直接将左右两侧零散的块给重新排个序不就行了？
这样的时间复杂度就是 $O(n\sqrt{n}\log \sqrt{n})$

#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;
}

---

1. 设每个块的大小为 $B$ 个元素，那么我们总共有 $\frac{n}{B}$ 个块如果查询一个随机区间 $[L,R]$，则需要遍历 起始和结束的两个部分块，并直接使用 中间完整块 的预处理结果。由此可见此，查询的时间复杂度可以近似分解为以下两部分：遍历两个不完整块中的元素，复杂度为 $O(B)$ 查询中间完整块，复杂度为 $O(\frac{n}{B})$。
   所以，查询的总时间复杂度为：$O(B)+O(\frac{n}{B})$
   为了找到最优的块大小 $B$ ，我们可以将 $O(B)+O(\frac{n}{B})$ 视为一个函数，并对其求导来最小化它，
   令 $T(B)=B+\frac{n}{B}$ ，对 $T(B)$ 关于 $B$ 求导得 $T^{\prime }(B)$ 并设为0。
   则有 $T^{\prime }(B)=1-\frac{n}{B^2}=0$
   解这个方程的 $B=\sqrt{n}$ ↩︎

原文地址：https://blog.csdn.net/CylMK/article/details/143647593

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！