专栏文章

分块

mmincrafter_or_cy
算法·理论参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mir43ej8
此快照首次捕获于
2025/12/04 15:25
3 个月前
此快照最后确认于
2025/12/04 15:25
3 个月前
查看原文

分块

定义:

使用分治思想，将数据适当划分，在每一块上预处理部分信息，以获得较优的时间复杂度。
其时间复杂度主要取决于分块的块长，一般可通过 均值不等式 求出相应的最优块长及相应的时间复杂度。
优点：比线段树和树状数组灵活
缺点：比它们慢

一般的时间复杂度分析:

当 n/size=sizen /size = size 时，即 size=nsize = \sqrt n，O(n/size+size)=O(size+size)=O(size)O( n / size + size ) = O( size + size ) = O (size)。

分块的大小：

一般的块的大小 size=n(±1)size = \sqrt n (\pm 1)，则块的数量 tot=(n+size−1)/sizetot = ( n + size - 1 ) / size。

实现:

数组定义：
假设问题是求区间和。
nn是原序列的大小， sizesize 是块的大小， tottot 是块数， s[i]、t[i]s[i] 、 t[i] 分别是第 ii 块的头 和 尾, sum[i]、tag[i]sum[i]、tag[i] 分别是第 ii 块的区间和 和 标记, bein[i]bein[i] 表示第 ii 个数在哪一块， a[i]a[i] 是原序列。
初始化分块：
将一个序列按 sizesize 分成 kk 个子块，若序列大小不是 sizesize 的倍数，则剩余一个 “碎块”。
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]
若 ll 和 rr 在同一个块内，直接暴力 O(size)O( size )。
否则答案由三个部分组成：以 ll 开头的不完整块，中间一个完整块，以 rr 结尾的不完整块。 对于完整块，利用已经维护的答案；对于不完整块，继续暴力。最坏复杂度 O(n/size+size)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]
若 ll 和 rr 在同一个块内，直接暴力 O(size)O( size )。
否则答案由三个部分组成：以 ll 开头的不完整块，中间一个完整块，以 rr 结尾的不完整块。 对于完整块，修改维护的答案；对于不完整块，继续暴力，同时修改维护的答案。最坏复杂度 O(n/size+size)O( n / size + size )。
加上一个数 kk
若减去 kk 则 k=−kk = - 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;
     }
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...