数列分块学习笔记

算法讲解

分块是一种很暴力的数据结构，它的思想主要是通过将序列分成长度为 $\sqrt n$ 的许多块来分别处理来保证时间复杂度为 $n\sqrt n$。

分块的实现十分简单，下面就以最基础的区间加法为例。

例题

首先我们需要初始化出每一块的左端点、右端点还有原数组中每一个位置所对应的块编号。为了方便，我们用 $L_i$ 和 $R_i$ 表示第 $i$ 块的左端点和右端点；$sum_i$ 表示第 $i$ 块的和；$lasy_i$ 表示第 $i$ 块应该整体加上多少；$who_i$ 表示原数组中第 $i$ 个位置对应的块编号。那么预处理代码如下：

int n,m;
long long a[100005];
int blo,L[100005],R[100005],who[100005]; // 块数/块长、每一块的左右端点、原序列每一个位置对应的块编号 
long long sum[100005]; // 每一块的和
long long lazy[100005]; // 每一块整体应该加上多少

inline void init()
{
	blo=sqrt(n);
	for(int i=1;i<=blo;i++) // 预处理出每一块的左右端点 
	{
		L[i]=R[i-1]+1;
		R[i]=L[i]+blo-1;
	}
	R[blo]=n; // 最后一块的右端点特殊处理
	for(int i=1;i<=n;i++)
	{
		who[i]=(i-1)/blo+1; // 预处理出原数组每个位置对应的块编号 
		sum[who[i]]+=a[i]; // 预处理出每一块的和
	}
}

接下来，我们需要考虑怎么处理区间加操作。假设当前需要把 $[l,r]$ 加上 $k$，那么对于 $[l,r]$ 中整块的部分，可以将它们的 $lazy_i$ 直接加上 $k$；对于两边不满一块的部分，可以把它们的 $a_i$ 分别加上 $k$，因为不满一块的长度不会超过 $\sqrt n$，所以时间复杂度是正确的。

区间加的代码如下：

inline void add(int l,int r,long long k)
{
	if(who[l]==who[r]) // 同一块内 
	{
		for(int i=l;i<=r;i++)
		{
			a[i]+=k;
		}
		return;
	}
	// 不满一块的部分暴力处理 
	for(int i=l;i<=R[who[l]];i++)
	{
		a[i]+=k;
	}
	for(int i=L[who[r]];i<=r;i++)
	{
		a[i]+=k;
	}
	// 中间的整块直接加上 
	for(int i=who[l]+1;i<=who[r]-1;i++)
	{
		lazy[i]+=k;
	}
}

最后，询问的处理也呼之欲出了。只需要仿照区间加来操作就行了，不过注意要加上 $lazy$ 值。

询问的代码如下：

inline long long que(int l,int r)
{
	if(who[l]==who[r]) // 同一块内 
	{
		long long res=0;
		for(int i=l;i<=r;i++)
		{
			res+=a[i]+lazy[who[l]]; // 不要漏了 lazy 
		}
		return res;
	}
	long long res=0;
	// 不满一块的部分暴力处理 
	for(int i=l;i<=R[who[l]];i++)
	{
		res+=a[i]+lazy[who[l]]; // 不要漏了 lazy 
	}
	for(int i=L[who[r]];i<=r;i++)
	{
		res+=a[i]+lazy[who[r]]; // 不要漏了 lazy 
	}
	// 中间的整块直接加上 
	for(int i=who[l]+1;i<=who[r]-1;i++)
	{
		res+=sum[i]+lazy[i]; // 不要漏了 lazy 
	}
}

完整代码如下，是不是比线段树短很多，但是会 TLE，因为 $O(m \sqrt n)$ 的时间复杂度不够优秀。

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int n,m;
long long a[100005];
int blo,L[100005],R[100005],who[100005]; // 块数/块长、每一块的左右端点、原序列每一个位置对应的块编号 
long long sum[100005]; // 每一块的和
long long lazy[100005]; // 每一块整体应该加上多少

inline void init()
{
	blo=sqrt(n);
	for(int i=1;i<=blo;i++) // 预处理出每一块的左右端点 
	{
		L[i]=R[i-1]+1;
		R[i]=L[i]+blo-1;
	}
	R[blo]=n; // 最后一块的右端点特殊处理
	for(int i=1;i<=n;i++)
	{
		who[i]=(i-1)/blo+1; // 预处理出原数组每个位置对应的块编号 
		sum[who[i]]+=a[i]; // 预处理出每一块的和
	}
}

inline void add(int l,int r,long long k)
{
	if(who[l]==who[r]) // 同一块内 
	{
		for(int i=l;i<=r;i++)
		{
			a[i]+=k;
		}
		return;
	}
	// 不满一块的部分暴力处理 
	for(int i=l;i<=R[who[l]];i++)
	{
		a[i]+=k;
	}
	for(int i=L[who[r]];i<=r;i++)
	{
		a[i]+=k;
	}
	// 中间的整块直接加上 
	for(int i=who[l]+1;i<=who[r]-1;i++)
	{
		lazy[i]+=k;
	}
}

inline long long que(int l,int r)
{
	if(who[l]==who[r]) // 同一块内 
	{
		long long res=0;
		for(int i=l;i<=r;i++)
		{
			res+=a[i]+lazy[who[l]]; // 不要漏了 lazy 
		}
		return res;
	}
	long long res=0;
	// 不满一块的部分暴力处理 
	for(int i=l;i<=R[who[l]];i++)
	{
		res+=a[i]+lazy[who[l]]; // 不要漏了 lazy 
	}
	for(int i=L[who[r]];i<=r;i++)
	{
		res+=a[i]+lazy[who[r]]; // 不要漏了 lazy 
	}
	// 中间的整块直接加上 
	for(int i=who[l]+1;i<=who[r]-1;i++)
	{
		res+=sum[i]+lazy[i]; // 不要漏了 lazy 
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	while(m--)
	{
		int type,l,r;
		scanf("%d%d%d",&type,&l,&r);
		if(type==1)
		{
			long long k;
			scanf("%lld",&k);
			add(l,r,k);
		}
		else
		{
			printf("%lld\n",que(l,r));
		}
	}
	return 0;
}

练习题目

由乃打扑克

链接

这题比较简单，主体思路就是二分套二分再加上排序什么的乱搞一通。

建议先做完P2801 教主的魔法再来做这题。（双倍经验）

初始化

链接

这题有点难，要对长度为 $x$ 的每次询问弄前缀和和后缀和，不过不怎么卡常，代码也是相当地短。