xy0v0's Blog

Back

什么是分块#

用于实现区间更新与区间查询的数据结构,可用于骗分。

相较于BIT、线段树等数据结构虽速度较慢,但更加灵活,多种问题均可转化为分块

分块的具体实现(单点修改)#

使用查询区间最大值的实现来举例:

定义数组 aia_i 为原始输入,bib_i 代表 ii 号元素对应的块编号,bmkbm_k 代表 kk 号块对应的块内最大值。

要对于一个区间 [l,r][l,r] 进行区间查询,首先需要注意** ll 与 rr 是否在同一块内**。如果不在同一块内,首先记录左侧端点所在块号 blb_l 与右侧端点所在块号 brb_r ,遍历从 ll 到所在块号为 blb_l 的最后一个元素,右端点附近处理方式同理。接下来遍历中间块,即块编号在 [bl+1,br−1][b_l+1,b_r-1] 中的所有块的 bmbm 。

需要注意的是,以上操作仅支持单点修改,未考虑区间修改。

代码实现(单点修改)#

块编号预处理/输入处理#

int B=sqrt(n)+1; // 块总数
for(int i=1;i<=n;i++) b[i]=(i-1)/B+1;
for(int i=1;i<=n;i++){
	cin>>a[i];
	bm[b[i]]=max(bm[b[i]],a[i]);
}
cpp

其中我们令总块数为 n\sqrt{n} 。可以证明,取块数为 n\sqrt{n} 时最优,下面给出简单证明:

考虑最坏情况,即遍历一个块长度的离散元素和 nB\frac nB 个块,时间复杂度为 B+nBB+\frac nB 。考虑基本不等式,显然 B>0B > 0 ,则 B+nBB+\frac nB 在 B=nBB =\frac nB 即 B=nB=\sqrt{n} 时取得最小值。

区间查询#

int rmq(int l,int r){
	int res=-INF;
	if(b[l]==b[r]){
		res=*max_element(a+1+l,a+1+r);
		return res;
	}
	else{
		for(int i=l;b[i]==b[l];i++) res=max(res,a[i]);
		for(int i=b[l]+1;i<=b[r]-1;i++) res=max(res,bm[i]);
		for(int i=r;b[i]==b[r];i--) res=max(res,a[i]);
	}
	return res;
}
cpp

实现区间修改#

参考线段树中的 lazytag ,实现区间修改,定义 ckc_k 为 kk 号块的偏移量。

每次区间修改类似于区间查询,先判断是否在同一块,再修改两边元素和中间的 lazytag 。

区间修改代码实现#

区间修改#

区间查询(添加 lazytag)#

tips:warn
代码虽逻辑简单,但其中部分细节需要特别注意,比如区分元素编号与块编号。
plaintext

例题1(区间内特定值域内元素计数)#

长城上共有n个防御塔。第i个防御塔的防御力为 aia_i 。在你的作战指挥部里,你正在模拟m种轰炸方式。第j种轰炸方式的攻击范围从第 ljl_j 个防御塔炸到第 rjr_j 个,攻击力为 kjk_j 。其中防御力小于等于 kjk_j 的塔都会被摧毁。请对每种轰炸方式,计算能炸毁几个塔。

思路分析#

对于这种问题,我们可以考虑块内排序后再在块内进行二分查找。由于每个块的处理时间发生改变,我们的块数需要重新计算。

每个分块查询进行一次二分,单个分块的时间复杂度为 O(log⁡B)O(\log B) ,共有 BB 块,最坏情况为 B+nlog⁡BBB + \frac {n \log B}B 。则有 B=nlog⁡B≈nlog⁡nB=\sqrt{n \log B} \approx \sqrt{n \log n} 。

代码#

例题2(实时排名)#

大赛共 nn 位选手。决赛只有一题一次网络提交机会,nn 位选手依次提交,第 nn 个提交的选手显示出得分为 xix_i ,即刻他的分数就会记录到得分排行榜上,对于每个选手请你求出他提交的时刻是当时第几名?可能名次并列。 输入一行为正整数n,2<=n<=200000。接着一行为n个非负整数,第i个数为xi,均不超过10000

这题我们需要转变思路,不一定需要对选手编号进行分块,而是对分数进行分块。但是这需要数据的最大值较小,观察到这道题中 xix_i 均不超过10000,因此可对分数进行分块。

代码#

tips:info
其实这道题使用后续的BIT做更方便,放在这为了展示分块算法的灵活性,分块的对象不仅限于编号。
plaintext