分块

技术分享 12个月前 (02-16) 0 999+

关注

分块

特点：一种优雅的暴力，大段维护，小段朴素。

假设我们有一个长度为 (n) 的数组 (a)。

需要我们维护区间修改和区间查询等操作。

那么朴素算法就不用说了，如果是万能的线段树还行。但是线段树码量过大，容易出bug。

这个时候就得用到分块的思想。

分块思想：

对于需要维护的数组 (a)，将其分为 (num) 块，每一块块长为 (block)，然后对每一块进行维护，最后求解。

那么这个 (block) 是多少好呢？

根据均值不等式，当 (frac{n}{block}=block)，即当 (block=sqrt{n}) 时最优，单次修改为 (O(sqrt{n}))。

显然有些情况下，(nmod block neq 0)，即分完会有剩下的元素。那么很显然可以将块数 (+1)，就当作是新建一块。

对于每个块的维护

可以建立一个结构体来存放每一个快。

内存块的左端点、右端点、区间和。如果题目中有区间修改，那么类似的，放一个懒标记进去，表示该区间所有数都要加上多少。

对于第 (i) 块 ((forall 1le ile num))：

左端点 (=(i-1)lfloor{sqrt{n}}rfloor+1)，右端点是 (min (ilfloor{sqrt{n}}rfloor,n))。因为有可能 (nmod block neq 0)。

下面就是一个例子：

其中：

[(1le i le n) \ l_i=left{1,5,9,13,17right} \ r_i=left{4,8,12,16,17right} ]

对于每个下标 (i)，用 (belong_i) 表示第 (i) 号元素属于第 (belong_i) 块。

操作维护

设 (l,r) 分别是增加区间的左右端点，增加 (d)。

若 (belong_l=belong_r)，即在同一个块中：

将所有的 (a_i) 加上 (d)，再将 (sum_ileftarrow sum_i+d(r-l+1))。（小段朴素）

否则，设 (belong_l=q,belong_r=p)：

对于区间 ([l,r_q])，用同一个块中的方法进行维护。

即维护下图的区间 ([2,4])。

同理，也可以维护区间 ([l_p,r])，即上图区间 ([13,14])。

现在我们已经解决了区间 ([2,4]) 和 ([13,14])，还剩下在两个区间中间的区间 ([5,8]) 和 ([9,12])。

显然 ([5,8]) 和 ([9,12]) 是两个块，就将块的懒标记全部加上 (d) 即可。

若不用懒标记，像小区间那样的朴素维护，很容易时间就超了。

代码部分

例题：P3374 【模板】树状数组 1。

一个块的元素：

struct NODE{ 		ljl l,r,sum; 	}node[N];

建立块：

void build() 	{ 		block=floor(sqrt(n)); 		num=n/block; 		if(n%block!=0) ++num;//不能分为整块 		for(ljl i=1;i<=num;++i) 		{ 			node[i].l=(i-1)*block+1,node[i].r=min(i*block,n);//公式已说 			for(ljl j=node[i].l;j<=node[i].r;++j) 				node[i].sum+=a[j]; 		} //		for(ljl i=1;i<=num;++i) //			cout<<node[i].l<<' '<<node[i].r<<" "<<node[i].sum<<'n'; 		for(ljl i=1;i<=n;++i) 			belong[i]=(i-1)/block+1; 		return; 	}

单点修改：

void update(ljl x,ljl y) 	{ 		a[x]+=y; 		node[belong[x]].sum+=y; 		return; 	}

区间查询：

ljl query(ljl l,ljl r) 	{ 		ljl q=belong[l],p=belong[r]; 		if(q==p) 		{ 			ljl ans=0; 			for(ljl i=l;i<=r;++i) 				ans+=a[i]; 			return ans; 		} 		ljl ans=0; 		for(ljl i=l;i<=node[q].r;++i) 			ans+=a[i]; 		for(ljl i=q+1;i<=p-1;++i) 			ans+=node[i].sum; 		for(ljl i=node[p].l;i<=r;++i) 			ans+=a[i]; 		return ans; 	}

完整代码：

#include<bits/stdc++.h> using namespace std; #define ljl long long const ljl N=5e5+5; ljl n,m,a[N],block; namespace BLOCK{ 	struct NODE{ 		ljl l,r,sum; 	}node[N]; 	ljl belong[N],num; 	void build() 	{ 		block=floor(sqrt(n)); 		num=n/block; 		if(n%block!=0) ++num; 		for(ljl i=1;i<=num;++i) 		{ 			node[i].l=(i-1)*block+1,node[i].r=min(i*block,n); 			for(ljl j=node[i].l;j<=node[i].r;++j) 				node[i].sum+=a[j]; 		} //		for(ljl i=1;i<=num;++i) //			cout<<node[i].l<<' '<<node[i].r<<" "<<node[i].sum<<'n'; 		for(ljl i=1;i<=n;++i) 			belong[i]=(i-1)/block+1; 		return; 	} 	void update(ljl x,ljl y) 	{ 		a[x]+=y; 		node[belong[x]].sum+=y; 		return; 	} 	ljl query(ljl l,ljl r) 	{ 		ljl q=belong[l],p=belong[r]; 		if(q==p) 		{ 			ljl ans=0; 			for(ljl i=l;i<=r;++i) 				ans+=a[i]; 			return ans; 		} 		ljl ans=0; 		for(ljl i=l;i<=node[q].r;++i) 			ans+=a[i]; 		for(ljl i=q+1;i<=p-1;++i) 			ans+=node[i].sum; 		for(ljl i=node[p].l;i<=r;++i) 			ans+=a[i]; 		return ans; 	} } using namespace BLOCK; int main(){ 	ios::sync_with_stdio(0); 	cin>>n>>m; 	for(ljl i=1;i<=n;++i) 		cin>>a[i]; 	build(); //	for(ljl i=1;i<=n;++i) //		cout<<belong[i]<<' '; //	cout<<"n"; 	while(m--) 	{ 		ljl op,x,y; 		cin>>op>>x>>y; 		if(op==1) 			update(x,y); 		else 		{ 			cout<<query(x,y)<<'n'; 		} //		cout<<"--------------n"; //		for(ljl i=1;i<=num;++i) //			cout<<node[i].l<<" "<<node[i].r<<" "<<node[i].sum<<'n'; //		cout<<"----------------n"; 	} 	return 0; }

例题二：P3372 【模板】线段树 1。

因为上一题仅仅是单点修改，过于简单。

所以上强度：

本题需要区间修改和区间查询，具体看代码：

#include<bits/stdc++.h> using namespace std; #define ljl long long const ljl N=1e5+5,BLOCKS=1e3+5; ljl n,a[N],q,l,r,v; namespace BLOCK{ 	struct NODE{ 		ljl l,r,sum,lz; 	}node[BLOCKS]; 	ljl belong[N],num,block; 	void build()//建块 	{ 		block=(ljl)sqrt(n); 		num=n/block; 		if(n%block)++num; 		for(ljl i=1;i<=num;++i) 		{ 			node[i].l=(i-1)*block+1,node[i].r=min(i*block,n); 			for(ljl j=node[i].l;j<=node[i].r;++j) 				node[i].sum+=a[j]; 		} 		for(ljl i=1;i<=n;++i) 			belong[i]=(i-1)/block+1; 		return; 	} 	void change_part(ljl id,ljl l,ljl r)//对于是一个块内的区间修改 	{ 		for(ljl i=l;i<=r;++i) 			a[i]+=v; 		node[id].sum+=v*(r-l+1); 	} 	void change(ljl l,ljl r)//询问的区间修改 	{ 		ljl q=belong[l],p=belong[r]; 		if(q==p) 		{ 			change_part(q,l,r);return; 		} 		change_part(q,l,node[q].r);//按照上文讲过的方法实现即可 		change_part(p,node[p].l,r); 		for(ljl i=q+1;i<p;++i) 			node[i].lz+=v;//这里是懒标记 		return; 	} 	ljl query_part(ljl id,ljl l,ljl r) 	{ 		ljl ans=0; 		for(ljl i=l;i<=r;++i) 			ans=ans+(a[i]+node[id].lz); 		return ans; 	} 	ljl query(ljl l,ljl r) 	{ 		ljl q=belong[l],p=belong[r]; 		if(q==p) 			return query_part(q,l,r); 		ljl ans=0; 		ans+=query_part(q,l,node[q].r); 		ans+=query_part(p,node[p].l,r); 		for(ljl i=q+1;i<p;++i) 			ans=ans+node[i].sum+(node[i].r-node[i].l+1)*node[i].lz; 		return ans;		 	} } using namespace BLOCK; int main(){ 	ios::sync_with_stdio(0); 	cin>>n>>q; 	for(ljl i=1;i<=n;++i) 		cin>>a[i]; 	build(); 	while(q--) 	{ 		ljl op; 		cin>>op; 		if(op==1) 		{ 			cin>>l>>r>>v; 			change(l,r); 		} 		else 		{ 			cin>>l>>r; 			cout<<query(l,r)<<'n'; 		} 	} 	return 0; }