分块学习笔记

分块详细教程来啦!

阅读全文大概需要 8分钟
本文总阅读量
Posted by yjjr's blog on February 3, 2018

根号平衡

根号类算法的前置技能大多是根号平衡

有x次操作,单次复杂度为O(a)

有y=kx次查询,单次复杂度为O(b)

在满足一定条件的题里面

可以通过提高其中一边的复杂度,降低另一边的复杂度来达到更好的效果

这时有xa=kxb ==> 复杂度由ax+bkx=2x

根号分类

  • 静态分块
  • 动态分块

静态分块指的是放一些关键点,预处理关键点到关键点的信息来加速查询的,不能支持修改 如果可以离线,静态分块是莫队算法的子集

动态分块指的是把序列分为一些块,每块维护一些信息,可以支持修改

动态分块基础

要实现:

  1. 区间加
  2. 区间和

朴素的做法

  1. O(1)修改O(n)查询
  2. O(n)修改O(1)查询

显然这种暴力做法远远不满足要求的

\[这个问题可以套用根号平衡达到O(\sqrt n)修改O(\sqrt n)查询\] \[我们可以把\sqrt n个元素放一块里面维护\]

我们把每次操作完整覆盖的块定义为“整块” 把每次操作没有完整覆盖的快定义为“零散块” 如下图所示 这里写图片描述

\(每次操作最多经过O(\sqrt n)个整块,以及2个零散块\) \(所以我们可以O(1)维护整块信息,O(\sqrt n)查询零散块信息\) \(这样就达到了O(m \sqrt n)的复杂度\) \(每次修改只用更新:\sqrt n个size为1的节点以及2个size为\sqrt n的节点\)

经典问题总结

区间加-单点查询

直接套用分块即可,见LOJ6277

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=1e5+6;
int n,tnum,a[maxn],atag[maxn],b[maxn];
void add(int x,int y,int z){
	rep(i,x,min(b[x]*tnum,y))a[i]+=z;
	if(b[x]!=b[y])
		rep(i,(b[y]-1)*tnum+1,y)a[i]+=z;
	rep(i,b[x]+1,b[y]-1)atag[i]+=z;
}
int main(){
	n=read();tnum=sqrt(n);
	rep(i,1,n)a[i]=read();
	rep(i,1,n)b[i]=(i-1)/tnum+1;
	rep(i,1,n){
		int opt=read(),x=read(),y=read(),z=read(); 
		if(opt==0)add(x,y,z);else printf("%d\n",a[y]+atag[b[y]]);
	}
	return 0;
}
//a数组存储每个单点的值
//atag数组存储每个分块的标记值
//b数组为每个a对应的分块位置
//区间修改是只需要修改两个零散段的a数组和中间许多整段的atag标记值

区间加-查询区间小于x的数个数

LOJ6278

显然分治结构无法在理想的复杂度下解决这个问题

分块维护每块的OV(就是排序后的数组)

  • 区间加的时候每个零散块重构,整块可以打上标记
  • 查询的时候整块查询小于x的数,设这个整块的标记值为y,等价于查OV(整块排序后的数组)里面小于x-y的数个数,可以二分处理;零散块就暴力查询
\[此时的时间复杂度为O(m \sqrt n)\]

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=1e5+6;
int a[maxn],b[maxn],atag[maxn],n,tnum;
vector<int>v[maxn];
void reset(int x){
	v[x].clear();
	rep(i,(x-1)*tnum+1,min(x*tnum,n))v[x].push_back(a[i]);
	sort(v[x].begin(),v[x].end());
}
void add(int x,int y,int z){
	rep(i,x,min(b[x]*tnum,y))a[i]+=z;
	reset(b[x]);
	if(b[x]!=b[y]){
		rep(i,(b[y]-1)*tnum+1,y)a[i]+=z;
		reset(b[y]);
	}
	rep(i,b[x]+1,b[y]-1)atag[i]+=z;
}
int query(int x,int y,int z){
	int ans=0;
	rep(i,x,min(b[x]*tnum,y))if(a[i]+atag[b[x]]<z)ans++;
	if(b[x]!=b[y])
		rep(i,(b[y]-1)*tnum+1,y)if(a[i]+atag[b[y]]<z)ans++;
	rep(i,b[x]+1,b[y]-1)
		ans+=lower_bound(v[i].begin(),v[i].end(),z-atag[i])-v[i].begin();
	return ans;
}
int main()
{
	n=read();tnum=sqrt(n);
	rep(i,1,n)a[i]=read();
	rep(i,1,n){
		b[i]=(i-1)/tnum+1;
		v[b[i]].push_back(a[i]);
	}
	rep(i,1,b[n])sort(v[i].begin(),v[i].end());
	rep(i,1,n){
		int opt=read(),x=read(),y=read(),z=read();
		if(opt==0)add(x,y,z);else printf("%d\n",query(x,y,z*z));
	}
	return 0;
}

区间加-查询区间第k小

见lxl的毒瘤分块题[Ynoi2017]舌尖上的由乃

直接套用上一题的做法再二分加入一个Log的复杂度

很不幸,被老毒瘤卡掉了orz

\(将每个块的大小设为\sqrt n \log n\) \(显然每个修改操作的复杂度为O(\sqrt n \log n)\) \(查询操作转化为二分答案,那么存在\frac{ \sqrt n }{\log n}个整块,这部分的复杂度为O(\sqrt n)\) \(存在\sqrt n \log n个零散的点,这部分的复杂度为O(\sqrt n \log n),这样显然是不满足要求的\) \(可以预先先把零散的两个块归并成为一个假的块,这样我们每次二分答案之后只用在这个假的块上面二分即可\) \(总复杂度O(m\sqrt n\log n )\)

代码比较丑,就不贴了qwq

使用根号平衡优化数据结构

O(1)单点修改O(sqrt(n))区间和

分块维护块内和,每次修改的时候更新块内和与单点的值

查询的时候和普通分块一样

O(sqrt(n))单调修改O(1)区间和

分块分别维护块和的前缀和与块内数字的前缀和

更新的时候将这两个前缀和更新

查询的时候拼凑起来

O(1)区间加O(sqrt(n))查询单点

就是经典问题1相反复杂度的问题

用差分解决

同时在单点的数组和块上面打标记

查询的时候扫过块外和块内的标记即可

O(1)插入数O(sqrt(n))查询第k小

离散化,对值域进行分块

维护第i个块内有多少个数

查询从头跑一遍,最坏情况是跑完所有的整块和零散块

O(sqrt(n))插入数O(1)查询第k小

是上面的相反复杂度问题

同样对值域进行分块

对于每个数维护下在哪个块中

对于每个块维护一个OV(有序表)表示这个块内的所有数存在的数

从小到大这样我们修改的时候只会改变sqrt( n )个数所从属的块

查询的时候定位到其所属于的块,然后找到其在该块中对应的值

本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr