根号平衡
根号类算法的前置技能大多是根号平衡
有x次操作，单次复杂度为O(a)
有y=kx次查询，单次复杂度为O(b)
在满足一定条件的题里面
可以通过提高其中一边的复杂度，降低另一边的复杂度来达到更好的效果
这时有xa=kxb ==> 复杂度由ax+bkx=2x
根号分类
- 静态分块
- 动态分块
静态分块指的是放一些关键点，预处理关键点到关键点的信息来加速查询的，不能支持修改 如果可以离线，静态分块是莫队算法的子集
动态分块指的是把序列分为一些块，每块维护一些信息，可以支持修改
动态分块基础
要实现：
- 区间加
- 区间和
朴素的做法
- O(1)修改O(n)查询
- 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的数个数
显然分治结构无法在理想的复杂度下解决这个问题
分块维护每块的OV（就是排序后的数组）
- 区间加的时候每个零散块重构，整块可以打上标记
- 查询的时候整块查询小于x的数，设这个整块的标记值为y，等价于查OV（整块排序后的数组）里面小于x-y的数个数，可以二分处理；零散块就暴力查询
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