分块简介

分块的基本思想是通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。

如何分块

一般的，我们会把原数组分成块长为 \(\sqrt{n}\) 的几段，初始化的复杂度为 \(O(n)\) ，单次操作的复杂度是 \(O(\sqrt{n})\)​

P3372 【模板】线段树 1

参考题目可以发现，出题人貌似想让我们写线段树，于是我们考虑如何不写线段树，我们可以采用分块。

关于变量的一些定义：

\(block\)​ ：块长

\(tot\) ：总块数

\(L_i\) ：第 \(i\) 块的左端点

\(R_i\) ：第 \(i\) 块的右端点

\(pos_i\) ：第 \(i\) 个数在所在的块的编号

\(s_i\) ：第 \(i\) 块所有数字的和

\(tag_i\)​ ：第 \(i\) 块的加法标记，具体作用见下文

初始化：

首先我们定义块长为 \(\sqrt{n}\)

枚举每一个块，它的左端点就是上一块右端点的下一个元素，右端点就是 \(\min(i*block,n)\)

接下来枚举这个区块内的所有元素，用 \(s_i\) 记录总和，同时把这些元素的 \(pos\) 标记为这个块的编号

因为我们只遍历了一整个序列，所以预处理的复杂度是 \(O(n)\) 的

初始化部分代码

inline void build() {
	block=sqrt(n);
	while(++tot) {
		L[tot]=R[tot-1]+1;
		R[tot]=min(block*tot,n);
		for(int i=L[tot];i<=R[tot];++i)
			pos[i]=tot,s[tot]+=a[i];
		if(R[tot]==n)
			break;
	}
}

区间加法

我们要将 \(a_x \sim a_y\) 加上 \(val\) ，暴力复杂度显然是 \(O(n)\)​ ，考虑优化

如果 \(x,y\) 在同一个块，显然暴力加的复杂度不会超过 \(O(\sqrt{n})\) ，直接暴力即可

如果 \(x,y\)​​​​ 不在同一个块，我们可以把这个块分成两边的零散块与中间的整块分别处理

旁边的零散块直接暴力处理

对于中间的整块，更新每一个加法标记 \(tag\) ，同时更新这个块的和 \(s\) 即可

由于块长为 \(O(\sqrt{n})\) ，零散块的操作复杂度不会超过 \(O(2 \times \sqrt{n})\) ，整块的数量不会超过 \(\sqrt{n}\)​

所以这一部分的复杂度为 \(O(sqrt{n})\)​

区间加法代码：

inline void Plus(int x,int y,int val) {
	int l=pos[x],r=pos[y];
	if(l==r) { // 判断是否在同一块内
		for(int i=x;i<=y;++i)
			a[i]+=val,s[l]+=val; // 暴力加
	}
	else {
		for(int i=x;i<=R[l];++i)
			a[i]+=val,s[l]+=val; // 处理左边的零散块
		for(int i=l+1;i<=r-1;++i)
			tag[i]+=val,s[i]+=val*(R[i]-L[i]+1); // 处理中间的整块
		for(int i=L[r];i<=y;++i)
			a[i]+=val,s[r]+=val; // 处理右边的零散块
	}
}

区间查询

查询 \(\sum^{y}_{i=x}a_i\)​

如果 \(x,y\) 在同一个块，显然暴力查询的复杂度不会超过 \(O(\sqrt{n})\)​​ ，注意不要忘记加上加法标记

如果 \(x,y\)​ 不在同一个块，我们两边的零散块同样暴力处理，中间的整块直接累计和即可

同样，这一部分的时间复杂度为 \(O(\sqrt{n})\)

区间查询代码：

inline int query(int x,int y) {
	int l=pos[x],r=pos[y];
	int ans=0;
	if(l==r) { // 判断是否在同一块内
		for(int i=x;i<=y;++i)
			ans+=a[i]+tag[l]; // 暴力加
	}
	else {
		for(int i=x;i<=R[l];++i)
			ans+=a[i]+tag[l]; // 处理左边的零散块
		for(int i=l+1;i<=r-1;++i)
			ans+=s[i]; // 处理中间的整块(每一个整块的和都加上过tag)
		for(int i=L[r];i<=y;++i)
			ans+=a[i]+tag[r]; // 处理右边的零散块
	}
	return ans;
}

将以上代码结合起来，我们就可以用分块 AC 本题

完整代码：

#include <cmath>
#include <cstdio>
#define min(a,b) ((a)<(b)?(a):(b))
typedef long long ll;
using namespace std;
const int N=1e5+7;

ll a[N];
ll s[N],tag[N];
int L[N],R[N],pos[N];

int n,m,block,tot;

inline void build() {
	block=sqrt(n);
	while(++tot) {
		L[tot]=R[tot-1]+1;
		R[tot]=min(block*tot,n);
		for(int i=L[tot];i<=R[tot];++i)
			pos[i]=tot,s[tot]+=a[i];
		if(R[tot]==n)
			break;
	}
}

inline void Plus(int x,int y,ll val) {
	int l=pos[x],r=pos[y];
	if(l==r) { // 判断是否在同一块内
		for(int i=x;i<=y;++i)
			a[i]+=val,s[l]+=val; // 暴力加
	}
	else {
		for(int i=x;i<=R[l];++i)
			a[i]+=val,s[l]+=val; // 处理左边的零散块
		for(int i=l+1;i<=r-1;++i)
			tag[i]+=val,s[i]+=val*(R[i]-L[i]+1); // 处理中间的整块
		for(int i=L[r];i<=y;++i)
			a[i]+=val,s[r]+=val; // 处理右边的零散块
	}
}

inline ll query(int x,int y) {
	int l=pos[x],r=pos[y];
	ll ans=0;
	if(l==r) { // 判断是否在同一块内
		for(int i=x;i<=y;++i)
			ans+=a[i]+tag[l]; // 暴力加
	}
	else {
		for(int i=x;i<=R[l];++i)
			ans+=a[i]+tag[l]; // 处理左边的零散块
		for(int i=l+1;i<=r-1;++i)
			ans+=s[i]; // 处理中间的整块(每一个整块的和都加上过tag)
		for(int i=L[r];i<=y;++i)
			ans+=a[i]+tag[r]; // 处理右边的零散块
	}
	return ans;
}

signed main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%lld",a+i);
	build();
	for(int op,l,r;m;--m) {
		scanf("%d%d%d",&op,&l,&r);
		if(op==1) {
			ll k;
			scanf("%lld",&k);
			Plus(l,r,k);
		}
		else
			printf("%lld\n",query(l,r));
	}
    return 0;
}

习题

P2357 守墓人

与例题思想相近，稍加修改即可AC

P3870 [TJOI2009]开关

P5057 [CQOI2006]简单题

P2846 [USACO08NOV]Light Switching G

SP7259 LITE - Light Switching

P2574 XOR的艺术

区间异或，将模板稍微改一下就行，还可以收获5倍经验

P4145 上帝造题的七分钟 2 / 花神游历各国

区间开方与求和

求和直接用分块即可，那么怎么进行区间开方呢

注意到一个性质，一个数一直开方后总会变成 \(1\) 或 \(0\)

所以我们一开始先暴力开方，如果一段区间内所有的数都是 \(1\) 或 \(0\) ，那么这段区间不管怎么开方，它的每一个数都不会被改变，所以在修改时这段区间直接跳过就行

代码：

#include <cmath>
#include <cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
typedef long long ll;
using namespace std;
const int N=1e5+7;

ll a[N];
ll s[N];
int L[N],R[N],pos[N];
bool vis[N];

int n,m;
int block,tot;

inline void build() {
	block=sqrt(n);
	while(++tot) {
		L[tot]=R[tot-1]+1;
		R[tot]=min(n,block*tot);
		for(int i=L[tot];i<=R[tot];++i)
			pos[i]=tot,s[tot]+=a[i];
		if(R[tot]==n)
			break;
	}
}

inline void check(ll x) { // 判断这个块是否全为1或0
	if(vis[x])
		return ;
	for(int i=L[x];i<=R[x];++i)
		if(a[i]>1)
			return ;
	vis[x]=true;
}

inline void update(int x,int y) {
	int l=pos[x],r=pos[y];
	ll t;
	if(l==r) {
		if(!vis[l]) {
			for(int i=x;i<=y;++i) {
				s[l]-=a[i]-floor(sqrt(a[i]));
				a[i]=sqrt(a[i]);
			}
			check(l);
		}
	}
	else {
		for(int i=x;i<=R[l];++i) {
			s[l]-=a[i]-floor(sqrt(a[i]));
			a[i]=sqrt(a[i]);
		}
		check(l);
		for(int i=l+1;i<r;++i)
			if(!vis[i]) {
				for(int j=L[i];j<=R[i];++j) {
					s[i]-=a[j]-floor(sqrt(a[j]));
					a[j]=sqrt(a[j]);
				}
				check(i);
			}
		for(int i=L[r];i<=y;++i) {
			s[r]-=a[i]-floor(sqrt(a[i]));
			a[i]=sqrt(a[i]);
		}
		check(r);
	}
}

inline ll query(int x,int y) {
	int l=pos[x],r=pos[y];
	ll ans=0;
	if(l==r) {
		for(int i=x;i<=y;++i)
			ans+=a[i];
	}
	else {
		for(int i=x;i<=R[l];++i)
			ans+=a[i];
		for(int i=l+1;i<r;++i)
			ans+=s[i];
		for(int i=L[r];i<=y;++i)
			ans+=a[i];
	}
	return ans;
}

signed main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%lld",a+i);
	build();
	scanf("%d",&m);
	for(int op,l,r;m;--m) {
		scanf("%d%d%d",&op,&l,&r);
		if(op)
			printf("%lld\n",query(min(l,r),max(l,r)));
		else
			update(min(l,r),max(l,r));
	}
    return 0;
}