分块学习笔记 - 算法学习 | 123hh2 = Keep moving forward

# 分块

分块是一种将一些需要维护的数据划分为一些小块后，预处理每个小块的信息从而实现较暴力更优的复杂度的一种思想，优化后的复杂度一般是 $O(n \sqrt{n})$ 的

接下来从最简单的求区间和来看看分块的实现方法

对于一个长度为 $s$ 的序列 $a$ ，我们将这个序列分成连续的大小相同的 $b$ 块

注意最后一个块可能并不完整，但这并没有多大影响

那么我们可以维护每个块的所有元素之和，这样我们在查询区间 $[l,r]$ 的和时，就可以快速计算

如果 $l$ 和 $r$ 在一个块中，那么直接暴力求和即可，复杂度最坏为 $O(b)$

如果 $l$ 和 $r$ 不在一个块中，那么我们要求的区间一定能划分成以 $l$ 开头的不完整块 + 一些完整块 + 以 $r$ 结尾的不完整块，对完整的块，直接加上这个块的元素之和即可，不完整的块直接暴力求和，最坏复杂度为 $O(b + \frac{s}{b})$

根据均值不等式 $b+ \frac{s}{b} \geq 2 \sqrt{b \times \frac{s}{b}}$ 可知当 $b = \frac{s}{b}$ 时，不等式有最小值，即取块长为 $\sqrt{s}$ 时，复杂度最优

如果要对这个块进行单点修改的话，完全可以暴力更新序列的值和对应块维护的该块的值

对于区间修改，我们可以类比查询操作，对于不完整的块，我们直接暴力修改，对于完整的块，我们再维护一个该块加过的值 $k_{block_{i}}$ ，类似线段树的懒标记，查询的时候每个元素的真实值是 $a_i + k_{block_{i}}$

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=1e5+5;
	const int maxm=1e3+5;
	int len;// 块长
	int awa[maxn];
	int id[maxn];// 每个位置对应的块的编号
	int tag[maxm];// 完整块的加值情况
	int sum[maxm];// 块内元素和
	void add(int l,int r,int val)
	{
	int L=id[l],R=id[r];
	if(L==R)
	{
	for(int i=l;i<=r;i++) awa[i]+=val,sum[L]+=val;
	}
	else
	{
	for(int i=l;id[i]==L;i++) awa[i]+=val,sum[L]+=val;
	for(int i=L+1;i<=R-1;i++) tag[i]+=val,sum[i]+=val*len;
	for(int i=r;id[i]==R;i--) awa[i]+=val,sum[L]+=val;
	}
	}
	void query(int l,int r)
	{
	int L=id[l],R=id[r],ans=0;
	if(L==R)
	{
	for(int i=l;i<=r;i++) ans+=awa[i]+tag[L];
	}
	else
	{
	for(int i=l;id[i]==L;i++) ans+=awa[i]+tag[L];
	for(int i=L+1;i<=R-1;i++) ans+=sum[i];
	for(int i=r;id[i]==R;i--) ans+=awa[i]+tag[R];
	}
	cout<<ans<<endl;
	}
	signed main()
	{
	int n=read(),q=read();
	len=sqrt(n);// 块长为 len
	for(int i=1;i<=n;i++)
	{
	awa[i]=read();
	id[i]=(i-1)/len+1;
	sum[id[i]]+=awa[i];
	}
	while(q-->0)
	{
	int op=read(),l=read(),r=read();
	if(op==1)
	{
	int val=read();
	add(l,r,val);
	}
	else query(l,r);
	}
	return _123hh2;
	}

# 例题

P1975 [国家集训队] 排队

把序列分块后，对每个块进行排序，交换 $l$ 和 $r$ 位置的数相当于用 $l,r$ 比较 $[l+1,r-1]$ 区间内的数，不完整的块暴力查找，完整块二分查找即可

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=2e4+5;
	int awa[maxn],ans,len,n;
	vector<int> merge(int l,int r)
	{
	vector<int> now;
	now.push_back(awa[l]);
	if(l==r) return now;
	int mid=(l+r)/2;
	vector<int> a=merge(l,mid);
	vector<int> b=merge(mid+1,r);
	vector<int> c;
	int L=0,R=0;
	while(L!=a.size()&&R!=b.size())
	{
	if(a[L]>b[R]) ans+=a.size()-L,c.push_back(b[R]),R++;
	else c.push_back(a[L]),L++;
	}
	while(L!=a.size()) c.push_back(a[L]),L++;
	while(R!=b.size()) c.push_back(b[R]),R++;
	return c;
	}
	int id[maxn];
	struct A {int r,awa[201];}block[maxn];
	void deal(int l,int r)
	{
	int L=id[l],R=id[r];
	if(L==R)
	{
	for(int i=l+1;i<r;i++)
	{
	if(awa[l]>awa[i]) ans--;
	if(awa[l]<awa[i]) ans++;
	}
	for(int i=l;i<r;i++)
	{
	if(awa[r]>awa[i]) ans++;
	if(awa[r]<awa[i]) ans--;
	}
	swap(awa[l],awa[r]);
	return;
	}
	for(int i=l+1;id[i]==L;i++)
	{
	if(awa[l]>awa[i]) ans--;
	if(awa[l]<awa[i]) ans++;
	}
	for(int i=r-1;id[i]==R;i--)
	{
	if(awa[l]>awa[i]) ans--;
	if(awa[l]<awa[i]) ans++;
	}
	for(int i=l;id[i]==L;i++)
	{
	if(awa[r]>awa[i]) ans++;
	if(awa[r]<awa[i]) ans--;
	}
	for(int i=r-1;id[i]==R;i--)
	{
	if(awa[r]>awa[i]) ans++;
	if(awa[r]<awa[i]) ans--;
	}
	for(int i=L+1;i<R;i++)
	{
	int nl=1,nr=block[i].r,res=0;
	while(nl<=nr)
	{
	int mid=(nl+nr)/2;
	if(block[i].awa[mid]<awa[l]) res=mid,nl=mid+1;
	else nr=mid-1;
	}
	ans-=res;
	nl=1,nr=block[i].r,res=block[i].r+1;
	while(nl<=nr)
	{
	int mid=(nl+nr)/2;
	if(block[i].awa[mid]>awa[l]) res=mid,nr=mid-1;
	else nl=mid+1;
	}
	ans+=block[i].r-res+1;
	nl=1,nr=block[i].r,res=block[i].r+1;
	while(nl<=nr)
	{
	int mid=(nl+nr)/2;
	if(block[i].awa[mid]>awa[r]) res=mid,nr=mid-1;
	else nl=mid+1;
	}
	ans-=block[i].r-res+1;
	nl=1,nr=block[i].r,res=0;
	while(nl<=nr)
	{
	int mid=(nl+nr)/2;
	if(block[i].awa[mid]<awa[r]) res=mid,nl=mid+1;
	else nr=mid-1;
	}
	ans+=res;
	}
	for(int i=1;i<=block[L].r;i++)
	{
	if(block[L].awa[i]==awa[l])
	{
	block[L].awa[i]=awa[r];
	break;
	}
	}
	for(int i=1;i<=block[R].r;i++)
	{
	if(block[R].awa[i]==awa[r])
	{
	block[R].awa[i]=awa[l];
	break;
	}
	}
	swap(awa[l],awa[r]);
	sort(block[L].awa+1,block[L].awa+1+block[L].r);
	sort(block[R].awa+1,block[R].awa+1+block[R].r);
	}
	signed main()
	{
	n=read();
	len=sqrt(n);
	for(int i=1;i<=n;i++) awa[i]=read();
	for(int i=1;i<=n;i++)
	{
	id[i]=(i-1)/len+1;
	block[id[i]].r++;
	block[id[i]].awa[block[id[i]].r]=awa[i];
	}
	for(int i=1;i<=(n-1)/len+1;i++) sort(block[i].awa+1,block[i].awa+1+block[i].r);
	merge(1,n);
	cout<<ans<<endl;
	int q=read();
	while(q-->0)
	{
	int l=read(),r=read();
	if(l>r) swap(l,r);
	deal(l,r);
	cout<<ans<<endl;
	}
	return _123hh2;
	}

Block

# 分块

# 例题

2025-牛客多校5-Entangled-Coins

AtCoder Beginner Contest 418