分块
mincrafter_or_cy
·
·
算法·理论
分块
定义:
使用分治思想，将数据适当划分，在每一块上预处理部分信息，以获得较优的时间复杂度。
其时间复杂度主要取决于分块的块长，一般可通过 均值不等式 求出相应的最优块长及相应的时间复杂度。
优点：比线段树和树状数组灵活
缺点：比它们慢
一般的时间复杂度分析:
当 n /size = size 时，即 size = \sqrt n ， O( n / size + size ) = O( size + size ) = O (size) 。
分块的大小：
一般的块的大小 size = \sqrt n (\pm 1) ，则块的数量 tot = ( n + size - 1 ) / size 。
实现:
数组定义：
假设问题是求区间和。
$ size $ 是块的大小，
$ tot $ 是块数，
$ s[i] 、 t[i] $ 分别是第 $ i $ 块的头 和 尾,
$ sum[i]、tag[i] $ 分别是第 $ i $ 块的区间和 和 标记,
$ bein[i] $ 表示第 $ i $ 个数在哪一块，
$ a[i] $ 是原序列。
__初始化分块：__
将一个序列按 $ size $ 分成 $ k $ 个子块，若序列大小不是 $ size $ 的倍数，则剩余一个 “碎块”。
```cpp
for(int i=1;i<=tot;i++){
s[i]=(i-1)*size+1;
t[i]=min(i*size,n);
}
```
__初始化某数在哪块：__
```cpp
for(int i=1;i<=n;i++)
bein[i]=(i-1)/size+1;
```
__查询：$ [l,r] $__
若 $ l $ 和 $ r $ 在同一个块内，直接暴力 $ O( size ) $。
否则答案由三个部分组成：以 $ l $ 开头的不完整块，中间一个完整块，以 $ r $ 结尾的不完整块。
对于完整块，利用已经维护的答案；对于不完整块，继续暴力。最坏复杂度 $ O( n / size + size ) $。
```cpp
int getsum(int x,int y){
int ret=0;
if(bein[x]==bein[y]){
for(int i=x;i<=y;i++) ret+=a[i]+tag[bein[x]];
return ret;
}
for(int i=x;i<=t[bein[x]];i++) ret+=a[i]+tag[bein[x]];
for(int i=s[bein[y]];i<=y;i++) ret+=a[i]+tag[bein[y]];
for(int i=bein[x]+1;i<y;i++) ans+=sum[i];
return ret;
}
```
__修改：$ [l,r] $__
若 $ l $ 和 $ r $ 在同一个块内，直接暴力 $ O( size ) $。
否则答案由三个部分组成：以 $ l $ 开头的不完整块，中间一个完整块，以 $ r $ 结尾的不完整块。
对于完整块，修改维护的答案；对于不完整块，继续暴力，同时修改维护的答案。最坏复杂度 $ O( n / size + size ) $。
__加上一个数 $ k $__
若减去 $ k $ 则 $ k = - k $。
```cpp
void add(int x,int y,int k){
if(bein[x]==bein[y]){
for(int i=x;i<=y;i++){
a[i]+=k;
sum[bein[x]]+=k;
}
return;
}
for(int i=x;i<=t[bein[i]];i++){
sum[i]+=k;
a[i]+=k;
}
for(int i=bein[x]+1;i<bein[r];i++){
tag[i]+=k;
sum[i]+=size*k;
}
for(int i=s[bein[y]];i<=r;i++){
a[i]+=k;
sum[bein[y]]+=k;
}
}
```