• 欢迎光临~
> > 序列分块入门

序列分块入门

开发技术 开发技术 2022-12-27 次浏览

本文不涉及 Ynoi 大分块。

分块简介

对于一道数据结构题，如果常规思路（如线段树、BIT、ST 表、主席树、平衡树、树套树、K-D Tree 等）不好做，我们可以考虑将序列分成 (B) 块，进行区间 修改/询问 的时候散块暴力，整块通过一些奇妙的操作做到更优的复杂度。

(B) 一般取 (sqrt{n}) 或者 (sqrt{nlog n})。

这里给出将序列 (a) 分成 (texttt{blk}) 块。第 (i) 个块是 ([texttt{bl}_i,texttt{br}_i])。(a_i) 归属块 (texttt{bel}_i)。第 (i) 个块有 (texttt{bs}_i) 个元素（即块长）。

blk=分块个数
for(int i=1;i<=blk;i++){bl[i]=n/blk*(i-1)+1;br[i]=n/blk*i;}
br[blk]=n;
for(int i=1;i<=blk;i++){
	for(int j=bl[i];j<=br[i];j++){bel[j]=i;bs[i]++;}
}

约定几个名词：

  • 整块：指区间中间的几个完整的块。
  • 散块：指区间左右端的非完整块。
  • 标记：又称懒标记(Lazy Tag)，指修改不方便时，通过一个标记来保存修改状态，等到合适的实际和值进行合并。一般用于线段树中。

例题选讲

洛谷P3374 【模板】树状数组 1

给你一个长为 (n) 的序列，有 (m) 个操作，支持：

  • 1 x k 将第 (x) 个元素加上 (k)。
  • 2 x y 输出区间 ([x,y]) 的和。

(1 leq n,m leq 5times10^5)。

首先对原序列进行分块。我们在维护序列的同时维护每个块的块内和。

对于 1 操作，我们更新原序列和它所属的块的块内和。时间复杂度 (O(1))。

对于 2 操作，如果区间在一个块内我们就直接暴力搞，否则我们把区间分成三段：

  • 左边的散块 ([l,texttt{br}[texttt{bel}[l]]) 和右边的散块 ([texttt{bl}[{texttt{bel}[r]}],r]) 我们直接暴力搞。
  • 中间的整块，由于是几个完整的块，我们直接将所有块的块内和累加。

时间复杂度 (O(frac{n}{B}+B))，取 (B=sqrt{n}) 最优，为 (O(sqrt{n}))。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5+5,BL = 5e3+5;
int a[N],bl[BL],br[BL],bel[N],bs[BL],val[BL];
int n,blk,m;

inline void preworks(){
	blk=sqrt(n);
	for(int i=1;i<=blk;i++){bl[i]=n/blk*(i-1)+1;br[i]=n/blk*i;}
	br[blk]=n;
	for(int i=1;i<=blk;i++){
		for(int j=bl[i];j<=br[i];j++){bel[j]=i;bs[i]++;}
	}
	for(int i=1;i<=n;i++) val[bel[i]]+=a[i];
}

inline void update(int p,int v){
	a[p]+=v;
	val[bel[p]]+=v;
}

inline int query(int l,int r){
	if(bel[l]==bel[r]){
		return accumulate(a+l,a+r+1,0ll);
	}
	return accumulate(a+l,a+br[bel[l]]+1,0ll)+accumulate(a+bl[bel[r]],a+r+1,0ll)+accumulate(val+bel[l]+1,val+bel[r],0ll);
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	preworks();
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1) update(x,y);
		else cout<<query(x,y)<<'n';
	}
	return 0;
}

洛谷P3368 【模板】树状数组 2

给你一个长为 (n) 的序列，有 (m) 个操作，支持：

  • 1 x y k 将位于区间 ([x,y]) 的元素加上 (k)。
  • 2 x 输出第 (x) 个元素的值。

(1 leq n,m leq 5times10^5)。

这道题可以在上一道题的分块加上差分完成。但那就没有达到练习的目的了。

区间修改如果维护块内和的话散块和查询都不好搞，我们考虑引入线段树思想。给每一个块上打一个加法标记。修改的时候整块直接打标记，散块暴力改。单点查询的时候将原序列的值加上所在块的标记值即可。

查询时间复杂度 (O(1)) ，修改时间复杂度 (O(frac{n}{B}+B))，取 (B=sqrt{n}) 最优，为 (O(sqrt{n}))。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5+5,BL = 5e3+5;
int a[N],bl[BL],br[BL],bel[N],bs[BL],tag[BL];
int n,blk,m;

inline void preworks(){
	blk=sqrt(n);
	for(int i=1;i<=blk;i++){bl[i]=n/blk*(i-1)+1;br[i]=n/blk*i;}
	br[blk]=n;
	for(int i=1;i<=blk;i++){
		for(int j=bl[i];j<=br[i];j++){bel[j]=i;bs[i]++;}
	}
}

inline void update(int l,int r,int v){
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++) a[i]+=v;
		return;
	}
	for(int i=l;i<=br[bel[l]];i++) a[i]+=v;
	for(int i=bel[l]+1;i<bel[r];i++) tag[i]+=v;
	for(int i=bl[bel[r]];i<=r;i++) a[i]+=v;
}

inline int query(int p){
	return a[p]+tag[bel[p]];
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	preworks();
	while(m--){
		int op,l,r,v;
		cin>>op>>l;
		if(op==1) {cin>>r>>v;update(l,r,v);}
		else cout<<query(l)<<'n';
	}
	return 0;
}

洛谷P1908 逆序对

对于位于 ([1,n]) 的两个数 (i,j)。如果 (i>j) 且 (a_i<a_j)，则称有序数对 ((i,j)) 是一对逆序对。

给出一个长为 (n) 的序列 (a)。输出这个序列中有多少对逆序对。

(1 leq n leq 5times10^5,1leq a_i leq 10^9)

逆序对是一个经典二维偏序问题。一般用树状数组解决。而树状数组能做的，分块当然可以做！

先离散化（貌似可以不离散化，不过我不会）

然后对值域分块，遍历序列，到 (a_i) 时将 (a_i) 插进值域分块，然后查询 (i-sum_{1}^{a_i})（即序号比它小，值比它大的元素个数）。累加即可。实现这个功能，只需要实现单点修改区间查询。

时间复杂度 (O(nsqrt{n}))。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5,BL = 5e3+5;
int a[N],bl[BL],br[BL],bel[N],bs[BL],val[BL];
int n,blk,m;
inline void preworks(){
	blk=sqrt(n);
	for(int i=1;i<=blk;i++){bl[i]=n/blk*(i-1)+1;br[i]=n/blk*i;}
	br[blk]=n;
	for(int i=1;i<=blk;i++){
		for(int j=bl[i];j<=br[i];j++){bel[j]=i;bs[i]++;}
	}
}
inline void update(int p,int v){
	a[p]+=v;
	val[bel[p]]+=v;
}
inline int query(int l,int r){
	if(bel[l]==bel[r]){
		return accumulate(a+l,a+r+1,0ll);
	}
	return accumulate(a+l,a+br[bel[l]]+1,0ll)+accumulate(a+bl[bel[r]],a+r+1,0ll)+accumulate(val+bel[l]+1,val+bel[r],0ll);
}
int rk[N];
struct node{
	int v,id;
	bool operator<(const node x) const {
		return v<x.v;
	}
} v[N];
int ans;
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){cin>>v[i].v;v[i].id=i;}
	stable_sort(v+1,v+n+1);
	for(int i=1;i<=n;i++) rk[v[i].id]=i;
	preworks();
	for(int i=1;i<=n;i++){update(rk[i],1);ans += (i-query(1,rk[i]));}
	cout<<ans;
	return 0;
}

洛谷P3372 【模板】线段树 1

给你一个长为 (n) 的序列，有 (m) 个操作，支持：

  • 1 x y k 将位于区间 ([x,y]) 的元素加上 (k)。
  • 2 x y 输出 ([x,y]) 的和。

(1 leq n,m leq10^5)。

这道题是区间修改区间查询。我们考虑将第一题和第二题的思路结合起来。既维护块内和，也维护加法标记。

对于修改操作，如果在同一块仍然暴力修改，否则对于左右散块暴力改，整块打标记。

对于查询操作，如果在同一块就暴力查询，否则左右散块暴力求和，整块直接用块内和加上标记乘上块长即可。记得暴力求和时需要加上标记。

修改和查询都是 (O(frac{n}{B}+B)) 的，取 (B=sqrt{n}) 最优，为 (O(sqrt{n}))。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5+5,BL = 1e3+5;
int a[N],bl[BL],br[BL],bel[N],bs[BL],val[BL],tag[BL];
int n,blk,m;

inline void preworks(){
	blk=sqrt(n);
	for(int i=1;i<=blk;i++){bl[i]=n/blk*(i-1)+1;br[i]=n/blk*i;}
	br[blk]=n;
	for(int i=1;i<=blk;i++){
		for(int j=bl[i];j<=br[i];j++){bel[j]=i;bs[i]++;}
	}
	for(int i=1;i<=n;i++) val[bel[i]]+=a[i];
}

void update(int l,int r,int v){
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++){a[i]+=v;val[bel[i]]+=v;}
		return;
	}
	for(int i=l;i<=br[bel[l]];i++){a[i]+=v;val[bel[i]]+=v;}
	for(int i=bel[l]+1;i<bel[r];i++){tag[i]+=v;}
	for(int i=bl[bel[r]];i<=r;i++){a[i]+=v;val[bel[i]]+=v;}
}

int query(int l,int r){
	int ret=0;
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++) ret+=(a[i]+tag[bel[i]]);
		return ret;
	}
	for(int i=l;i<=br[bel[l]];i++) ret+=(a[i]+tag[bel[i]]);
	for(int i=bel[l]+1;i<bel[r];i++) ret+=(tag[i]*bs[i]+val[i]);
	for(int i=bl[bel[r]];i<=r;i++) ret+=(a[i]+tag[bel[i]]);
	return ret;
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	preworks();
	while(m--){
		int op,x,y,v;
		cin>>op>>x>>y;
		if(op==1){cin>>v;update(x,y,v);}
		else cout<<query(x,y)<<'n';
	}
	return 0;
}

LibreOJ6278 数列分块入门 2

给你一个长为 (n) 的序列，有 (n) 个操作，支持：

  • 0 l r c 将位于区间 ([l,r]) 的元素加上 (c)。
  • 1 l r c 输出 ([l,r]) 中，有多少个元素小于 (c^2)。

(1leq nleq5times10^4)。

先考虑静态全局版本，如何查询一个序列有多少个元素小于 (c^2)？最朴素的思路是挨个找，但是这样子单次询问需要 (O(n)) 的时间。我们可以将其排序一遍后，每一次查询只需要二分即可。就可以做到预处理 (O(nlog n))，单次询问 (O(log n))。应该是最优的了。

然后考虑如何查询区间有多少个元素小于 (c^2)？我们将原序列分块，然后询问就可以看成散块暴力，整块执行我们刚才讨论的静态全局版本。就可以做到预处理 (O(nlog B))，单次询问 (O(B+frac{n}{B}log B))。

然后加上修改。同样使用打加法标记法。容易发现整块同时加上一个数，块内排序后顺序不变。因此每次修改只需要将散块所在的两个块重新排序即可。单次修改时间复杂度 (O(Blog B+frac{n}{B}))。

貌似 (B=sqrt{n}) 仍然最优，预处理 (O(nlogsqrt{n}))。单次操作为 (O(sqrt{n}logsqrt{n})=O(sqrt{n}log n))。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6+5,BL = 1e3+5;
int blk,bl[BL],br[BL],bs[BL],bel[N],a[N],add[BL];
vector<int> sorted[BL];
int n,q;

inline void sort(int p){
	sorted[p].clear();
	for(int i=bl[p];i<=br[p];i++) sorted[p].push_back(a[i]);
	stable_sort(sorted[p].begin(),sorted[p].end());
}

inline void preworks(){
	blk=sqrt(n);
	for(int i=1;i<=blk;i++){bl[i]=n/blk*(i-1)+1;br[i]=n/blk*i;}
	br[blk]=n;
	for(int i=1;i<=blk;i++){
		for(int j=bl[i];j<=br[i];j++){bel[j]=i;bs[i]++;}
	}
	for(int i=1;i<=blk;i++) sort(i);
}

inline void update(int l,int r,int v){
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++) a[i]+=v;
		sort(bel[l]);return;
	}
	for(int i=l;i<=br[bel[l]];i++) a[i]+=v;
	sort(bel[l]);
	for(int i=bl[bel[r]];i<=r;i++) a[i]+=v;
	sort(bel[r]);
	for(int i=bel[l]+1;i<bel[r];i++) add[i]+=v;
}

inline int query(int l,int r,int c){
	c=c*c;
	int ans=0;
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++) ans+=(a[i]+add[bel[i]]<c);
		return ans;
	}
	for(int i=l;i<=br[bel[l]];i++) ans+=(a[i]+add[bel[i]]<c);
	for(int i=bl[bel[r]];i<=r;i++) ans+=(a[i]+add[bel[i]]<c);
	for(int i=bel[l]+1;i<bel[r];i++){
		ans+=(lower_bound(sorted[i].begin(),sorted[i].end(),c-add[i])-sorted[i].begin());
	}
	return ans;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	q=n;
	for(int i=1;i<=n;i++) cin>>a[i];
	preworks();
	while(q--){
		int l,r,v;char op;
		cin>>op>>l>>r>>v;
		if(op=='0') update(l,r,v);
		else cout<<query(l,r,v)<<'n';
	}
	return 0;
}

LibreOJ6279 数列分块入门 3

给你一个长为 (n) 的序列，有 (n) 个操作，支持：

  • 0 l r c 将位于区间 ([l,r]) 的元素加上 (c)。
  • 1 l r c 输出 ([l,r]) 中 (c) 的前驱。

(1leq nleq10^5)。

注：一个数在一个序列中的前驱 就是序列中 最大的 比这个数小 的数。

和上一题差不多，也是预处理时将整块排序。修改时打标记+散块暴力排序。查询时散块暴力，整块的时候二分，如果没有找到比 (c) 小的，否则就找到最大的比 (c) 小的。最后将求得的值取最大值即可。

时间复杂度和上一题一样。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6+5,BL = 1e3+5;
int blk,bl[BL],br[BL],bs[BL],bel[N],a[N],add[BL];
vector<int> sorted[BL];
int n,q;

inline void sort(int p){
	sorted[p].clear();
	for(int i=bl[p];i<=br[p];i++) sorted[p].push_back(a[i]);
	stable_sort(sorted[p].begin(),sorted[p].end());
}

inline void preworks(){
	blk=sqrt(n);
	for(int i=1;i<=blk;i++){bl[i]=n/blk*(i-1)+1;br[i]=n/blk*i;}
	br[blk]=n;
	for(int i=1;i<=blk;i++){
		for(int j=bl[i];j<=br[i];j++){bel[j]=i;bs[i]++;}
	}
	for(int i=1;i<=blk;i++) sort(i);
}

inline void update(int l,int r,int v){
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++) a[i]+=v;
		sort(bel[l]);return;
	}
	for(int i=l;i<=br[bel[l]];i++) a[i]+=v;
	sort(bel[l]);
	for(int i=bl[bel[r]];i<=r;i++) a[i]+=v;
	sort(bel[r]);
	for(int i=bel[l]+1;i<bel[r];i++) add[i]+=v;
}

inline int query(int l,int r,int c){
	int ans=-1;
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++) {
			if(a[i]+add[bel[i]]<c) ans=max(ans,a[i]+add[bel[i]]);
		}
		return ans;
	}
	for(int i=l;i<=br[bel[l]];i++) {
		if(a[i]+add[bel[i]]<c) ans=max(ans,a[i]+add[bel[i]]);
	}
	for(int i=bl[bel[r]];i<=r;i++) {
		if(a[i]+add[bel[i]]<c) ans=max(ans,a[i]+add[bel[i]]);
	}
	for(int i=bel[l]+1;i<bel[r];i++){
		int v=lower_bound(sorted[i].begin(),sorted[i].end(),c-add[i])-sorted[i].begin();
		if(v == 0) continue;
		if(sorted[i][v-1]==(c-add[i])) v--;
		v = sorted[i][v-1];
		ans=max(ans,v+add[i]);
	}
	return ans;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	q=n;
	for(int i=1;i<=n;i++) cin>>a[i];
	preworks();
	while(q--){
		int l,r,v;char op;
		cin>>op>>l>>r>>v;
		if(op=='0') update(l,r,v);
		else cout<<query(l,r,v)<<'n';
	}
	return 0;
}

LibreOJ6281 数列分块入门 5

给你一个长为 (n) 的自然数序列，有 (n) 个操作，支持：

  • 0 l r c 将位于区间 ([l,r]) 的元素取平方根并向下取整。
  • 1 l r c 输出 ([l,r]) 的和。

(1 leq n leq 5times10^4)

平方根有一个性质，任意一个自然数在经过一定次数的开方向下取整后，一定是一个小于等于 (1) 的自然数。

于是修改操作，我们散块暴力，整块先判断这个块的所有元素是否小于等于 (1)（这个可以维护）。如果是就不必暴力了，如果不是就暴力开根。

查询操作就照例维护块内和，散块暴力整块累加块内和即可。

时间复杂度不会算，不过可以通过本题。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5+5,BL = 5e3+5;
int a[N],bl[BL],br[BL],bel[N],bs[BL],val[BL];
bool one[N];
int n,blk;

inline void preworks(){
	blk=sqrt(n);
	for(int i=1;i<=blk;i++){bl[i]=n/blk*(i-1)+1;br[i]=n/blk*i;}
	br[blk]=n;
	for(int i=1;i<=blk;i++){
		for(int j=bl[i];j<=br[i];j++){bel[j]=i;bs[i]++;}
	}
	for(int i=1;i<=n;i++) val[bel[i]]+=a[i];
}

inline void update(int l,int r){
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++){
			val[bel[i]]-=a[i];
			a[i]=sqrt(a[i]);
			val[bel[i]]+=a[i];
		}
		return;
	}
	for(int i=l;i<=br[bel[l]];i++){
		val[bel[i]]-=a[i];
		a[i]=sqrt(a[i]);
		val[bel[i]]+=a[i];
	}
	for(int i=bel[l]+1;i<bel[r];i++){
		if(one[i]) continue;
		one[i]=true;
		for(int j=bl[i];j<=br[i];j++){
			val[i]-=a[j];
			a[j]=sqrt(a[j]);
			val[i]+=a[j];
			if(a[j] > 1) one[i]=false;
		}
	}
	for(int i=bl[bel[r]];i<=r;i++){
		val[bel[i]]-=a[i];
		a[i]=sqrt(a[i]);
		val[bel[i]]+=a[i];
	}
}

inline int query(int l,int r){
	if(bel[l]==bel[r]){
		return accumulate(a+l,a+r+1,0ll);
	}
	return accumulate(a+l,a+br[bel[l]]+1,0ll)+accumulate(a+bl[bel[r]],a+r+1,0ll)+accumulate(val+bel[l]+1,val+bel[r],0ll);
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	preworks();
	for(int i=1;i<=n;i++){
		int op,l,r,c;
		cin>>op>>l>>r>>c;
		if(op==0) update(l,r);
		else cout<<query(l,r)<<'n';
	}
	return 0;
}

LibreOJ6282 数列分块入门 6

给你一个长为 (n) 的自然数序列，有 (n) 个操作，支持：

  • 0 l r c 将 (r) 插入到第 (l) 个元素前。
  • 1 l r c 输出第 (r) 个元素的值。

(1 leq n leq 10^5)

这道题如果直接用 vector 复杂度是 (O(n^2)) 的，难以通过本题（实际上无压力跑过）

我们考虑将序列分块，每个块用一个 vector 来维护。插入的时候找到对应块的 vector 插入。但是这样子如果不停地往一个块插入就直接退化成 (O(n^2)) 了。我们可以定义一个阈值 (alpha)，在每次插入后判断如果当前块长大于预期块长的 (alpha) 倍，就重构整个序列。询问就直接找到对应的块即可。

(alpha) 取 (7) 最优。

时间复杂度期望 (O(nsqrt{n}))。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int BL = 500;
const int alpha=7;

vector<int> arr[BL];
int n,blk;

void build(){
	vector<int> a;
	a.push_back(0);
	for(int i=1;i<=blk;i++){
		for(int j:arr[i]) a.push_back(j);
		arr[i].clear();
	}
	blk=sqrt(n);
	vector<int> bl(blk+1),br(blk+1);
	for(int i=1;i<=blk;i++){bl[i]=n/blk*(i-1)+1;br[i]=n/blk*i;}
	br[blk]=n;
	for(int i=1;i<=blk;i++){
		for(int j=bl[i];j<=br[i];j++) arr[i].push_back(a[j]);
	}
}

pair<int,int> getpos(int p){
	int vec=1,cursor=0;
	for(;cursor+arr[vec].size()<p;cursor+=arr[vec].size(),vec++);
	return make_pair(vec,p-cursor-1);
}

inline void insert(int p,int v){
	pair<int,int> ppos=getpos(p);
	arr[ppos.first].insert(arr[ppos.first].begin()+getpos(p).second,v);
	n++;
	if(arr[ppos.first].size()>(alpha*(n/blk))) build();
}

inline int query(int p){
	pair<int,int> ppos=getpos(p);
	return arr[ppos.first][ppos.second];
}

signed main(){
	cin>>n;
	blk=1;
	for(int i=1;i<=n;i++){
		int v;cin>>v;
		arr[blk].push_back(v);
	}
	build();
	const int m = n;
	for(int i=1;i<=m;i++){
		int op,l,r,c;
		cin>>op>>l>>r>>c;
		if(op==0) insert(l,r);
		else cout<<query(r)<<'n';
	}
	return 0;
}
程序员灯塔
转载请注明原文链接：序列分块入门
喜欢 (0)