分块
2024-06-19 20:57:10
发布于：四川
听说发笔记能精华，所以我来了。
写的不好，内容少，请见谅。
由于图挂了，所以在 这里看 吧。
分块是一种思想，并不是一种数据结构。
分块的思想，就是把数列适当的分成很多块，分别维护每个块内的信息。这虽然是一种很暴力的思想，但是比暴力快特别多。
对于查询，就是处理整块中的信息，然后再暴力枚举处理处理散块中的信息。
对于修改，和查询一样，先修改整块的信息，再暴力枚举修改散块中的信息。
下面是图：
对于整块就是红色，对于散块就是绿色：
分块的时间复杂度取决于块长，就比如我分的块长是 ，那么对于修改就是 ，对于查询也是 。
块长我一般用 ，但是根据 OI-wiki 上说的，应该用均值不等式求，但是我不会qwq。
分块的好处是他有时候短，并且比线段树和树状数组能支持的东西强（除了线段树的特色懒标记）。但是就是时间复杂度太高了。
比如线段树模板题，要求支持区间加与区间和查询，就可以用分块做了。
我们维护这个块内已经堆积的整体加，这个块内所有数的加和，然后再维护每个地方上的数（没有处理块内堆积的加和）。
对于查询，整块的话查红色块内的加和就可以了，散块的话查绿色块内的现在真实的数（数加上块堆积的整体加）。
对于修改，整块直接改标记，让标记加上修改的数，对于散块枚举所有数，让这个数单独加上修改。
我们就愉快的用分块水过线段树啦！
时间复杂度 ，明显劣于线段树的 ，但是他码量小。
P3372 代码：
#include <iostream>
#include <cmath>
#define int long long
using namespace std;
const int N=1e5+5,S=320+5;
int t;//块长
int a[N];
int v[S],tag[S]/*标记*/,cnt[S];//块
int find(int x/*下标从1开始*/){//第几个块
return (x+t-1)/t;//向上取整
}
signed main(){
int n,m;
cin >> n >> m;
t=sqrt(n);
for (int i=1;i<=n;++i){
scanf("%lld",&a[i]);
v[find(i)]+=a[i];
++cnt[find(i)];
}
int op;
int l,r,x,t1,t2,i,ans;
for (int _=0;_<m;++_){
scanf("%lld",&op);
if (op==1){//区间加
scanf("%lld%lld%lld",&l,&r,&x);
t1=find(l),t2=find(r);//块
if (t1==t2){//特判如果在一个块
for (i=l;i<=r;++i) a[i]+=x,v[find(i)]+=x;
continue;
}
for (i=t1+1;i<t2;++i) tag[i]+=x;
for (i=l;find(i)==t1;++i) a[i]+=x,v[find(i)]+=x;
for (i=r;find(i)==t2;--i) a[i]+=x,v[find(i)]+=x;
}else{
scanf("%lld%lld",&l,&r);
t1=find(l),t2=find(r);
ans=0;
if (t1==t2){
for (i=l;i<=r;++i) ans+=a[i];
printf("%lld\n",ans);
continue;
}
for (i=t1+1;i<t2;++i) ans+=v[i]+tag[i]*cnt[i];
for (i=l;find(i)==t1;++i) ans+=a[i]+tag[find(i)];
for (i=r;find(i)==t2;--i) ans+=a[i]+tag[find(i)];
printf("%lld\n",ans);
}
}
return 0;
}
其实分块还可以是静态的，解决的东西也多了。
如区间众数，可以 这样 处理。
如简介所说的，分块是个 思想，别把它看作数据结构来搞。
首先暴力肯定是模拟每个地方往后弹到了哪里然后继续往后弹。
可以先把他分成 块，维护每个数弹几次能弹出该块，和弹出该块后会跑到哪里。
先说查询，其实查询就是模拟一下每次跳到哪里了，答案加上跳了几次。
再说修改。显然修改是不会影响到其他块的，所以我们再把块内的东西重搞一遍。
对于构造这两个数组，“弹出该块后会跑到哪里”数组直接算可以吧，“弹几次能弹出该块”这个是可以递推出来的。所以构造这两个数组的时间复杂度是 。
所以总时间复杂度 。
代码：
//对于每个数，a[i]表示跳几步跳出块，b[i]跳出块后在哪里
#include <iostream>
#include <cmath>
using namespace std;
const int N=2e5+5,M=1e3+5;
int num[N],idx[N];
int a[N],b[N];
int main(){
int n;
cin >> n;
int m=sqrt(n);
for (int i=1;i<=n;++i){
idx[i]=(i-1)/m;
}
for (int i=1;i<=n;++i){
scanf("%d",&num[i]);
}
for (int i=n;i>=1;--i){//倒着预处理
if (i+num[i]>n/*弹飞*/ || idx[i+num[i]]!=idx[i]){
b[i]=i+num[i];
a[i]=1;
continue;
}
a[i]=a[i+num[i]]+1;
b[i]=b[i+num[i]];
}
int t;
cin >> t;
int op;
int i,x,ans;
for (int _=0;_<t;++_){
scanf("%d",&op);
if (op==1){
scanf("%d",&i);
++i;
ans=0;
while (i<=n){
ans+=a[i];
i=b[i];
}
printf("%d\n",ans);
}else{//爆改块内(x)
scanf("%d%d",&i,&x);
++i;
num[i]=x;
for (int j=i;j!=0 && idx[j]==idx[i];--j){
if (j+num[j]>n/*弹飞*/ || idx[j+num[j]]!=idx[j]){
b[j]=j+num[j];
a[j]=1;
continue;
}
a[j]=a[j+num[j]]+1;
b[j]=b[j+num[j]];
}
}
}
return 0;
}
练习：
给你一个数列，要求支持区间加法，区间内小于 数的个数。
给你一个数列，要求支持单点修改，求区间内第 大的数是什么。
对于最后一个问题，目前处于口胡状态。现在思路是对于每个块维护一个排好序的数列。对于修改，修改块内哪个数列（插入排序 实现）。对于查询，二分答案（区间是值域）然后 check，check 中二分每个块内有多少个小于 mid 的数，然后最后和 比较（类似 P10417），时间复杂度 。如果不可做就别做了。
有帮助，赞一个