分块大法好!

#膜分块


分块大法可以说是久仰大名了,分块是一个超级暴(N)力(B)的算法,听某姓大佬说,一般的区间问题都可以用她来解决,她可以完成几乎所有的区间更新和区间查询问题,但是效率比线段树等数据结构要差一些QWQ

一些名词的解释

区间:数列中一段连续的元素
区间操作:将区间[a,b]进行某些操作
块:我们将数列划分成若干个不相交的区间,每个区间称为一个块
整块:在一个区间操作时,完整包含于区间的块
不完整的块:在一个区间操作时,只有部分包含于区间的块,即区间左右端点所在的两个块

#思想


对于一个长度为n的序列,我们可以讲其中的元素分为M个连续的子序列,每块的长度自然就为N/M。我们在更新一段区间[l,r]是,可以先更新l到l所在块的右端点和r所在块的右端点到r。即下图中红色的区域,每块中最多有N/M个元素,所以这一操作的复杂度的为N/M。
这里写图片描述
然后我们在成段更新刚才更新的块中间的那些块(即上图中红色区域中间的那些块),这些块最多为N块,所以这一操作的复杂度为M。
总操作的复杂度即为M+N/M,根据均值不等式(基本不等式)可知,M=sqrt(n)时复杂度最新。

#建立分块


block代表每一块有多大,num代表一共有几块,belong[i] 代表原序列中第i个元素在第几块,l[i]代表第i块的左端点,r[i]代表第i块的右端点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int build()
{
block = sqrt(n);
num = n/block;
if(n%block)//除不尽,多出一块
num++;
for(int i;i<=n;i++)
belong[i] = (i-1)/block+1;
for(int i=1;i<=num;i++)
{
l[i] = (i-1)*block+1;
r[i] = i*block;
}
r[num] = n;//制定后一块的右端点为n
}