Splay是一种平衡树,它的代码复杂度和时间复杂度稍弱于Treap,但由于其可以支持区间操作,所以在实战中还是有许多用处。
我们先来看看Splay的定义和基本思路。
伸展树(Splay Tree),也叫分裂树,它能在O(log n)内完成插入、查找和删除操作。在伸展树上的一般操作都基于伸展操作:假设想要对一个二叉查找树执行一系列的查找操作,为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法, 在每次查找之后对树进行重构,把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。
它的优势在于不需要记录用于平衡树的冗余信息。
Ps:我们介绍的Splay是双旋操作Splay。
struct node{
int fa,siz,ct,val,son[2];
}T[MAXN];
//fa记录父亲节点,siz记录子树大小,val记录当前节点值,ct表示与当
//前节点值相同的点个数,son[2]记录其左儿子和右儿子。
1.clear:清空点k里的数据
void clear(int k){
T[k].siz=T[k].ct=T[k].fa=T[k].val=T[k].son[0]=T[k].son[1]=0;
}
2.up:统计k的子树大小
void up(int k){
T[k].siz=T[L].siz+T[R].siz+T[k].ct;
}
3.get:查询k是父亲的左儿子还是右儿子
int get(int k){
return T[T[k].fa].son[1]==k;
}
对于Splay来说,最重要的就是rotate旋转和splay伸展操作。
对于rotate操作,我们可以类比于Treap的旋转。
void rotate(int &k){
int fa=T[k].fa,gran=T[fa].fa;
int d1=get(k),d2=get(fa);
T[T[k].son[d1^1]].fa=fa;
T[fa].son[d1]=T[k].son[d1^1];T[k].son[d1^1]=fa;
T[k].fa=gran;T[fa].fa=k;
if(gran) T[gran].son[d2]=k;;
up(fa);up(k);
}
splay操作是Rotate的升级版,该函数将子节点旋转到根,来保持Splay的复杂度。
每次的splay操作,我们都将其旋转到根节点。对于Splay的伸展操作,我们需要进行讨论:
1.当旋转的点中有根节点时,可以直接进行旋转。
2.当点x和其父亲,祖父三点共线,则先旋转x的父亲,然后旋转x。
3.如果x和其父亲,祖父三点不共线,旋转两次x。
void splay(int k){
for(int fa;fa=T[k].fa;rotate(k))
if(T[fa].fa) rotate(get(fa)==get(k)?fa:k);
root=k;
}
删除操作需要进行讨论,如果对于值x存在多个,那直接将x所在节点k的size和ct减1即可。如果不是这样,我们继续讨论,如果k没有儿子,直接clear节点k即可。如果k只有一个儿子,就将它的儿子接上来即可。如果k有两个儿子,就将它的前驱接到它父亲上,然后将k的右儿子接到前驱上,这样就删去了k节点。
int find(int k,int val){ //先求出要删除点的位置,并进行splay伸展
if(!k) return 0;
if(val==T[k].val){
splay(k);return k;
}
return find(T[k].son[val>T[k].val],val);
}
void delet(int x){
int pl=find(root,x);
if(!pl) return;
if(T[root].ct>1){
T[root].ct--,T[root].siz--;return;
}
if(!T[root].son[1]&&!T[root].son[0]){
clear(root),root=0;return;
}
if(!T[root].son[1]||!T[root].son[0]){
int rt=root;
root=T[root].son[0]+T[root].son[1];
T[root].fa=0;clear(rt);return;
}
int rt=root;
pre(root,x);splay(dist);
T[T[rt].son[1]].fa=root;T[root].son[1]=T[rt].son[1];
clear(rt);up(root);T[root].fa=0;
return;
}
如求取前驱,后继等操作,类似于Treap
void insert(int &k,int val,int pos){ //插入操作
if(!k){
k=++sz;
T[k].ct=T[k].siz=1;T[k].fa=pos;T[k].son[0]=T[k].son[1]=0;T[k].val=val;
dist=k;return;
}
if(val==T[k].val){
dist=k;T[k].siz++;T[k].ct++;return;
}
if(val<T[k].val) insert(T[k].son[0],val,k);
if(val>T[k].val) insert(T[k].son[1],val,k);
up(k);
}
int searchRANK(int k,int x){ //查询x排在第几
if(!k) return 0;
if(x<T[k].val) return searchRANK(L,x);
if(x==T[k].val) return T[L].siz+1;
if(x>T[k].val) return T[L].siz+T[k].ct+searchRANK(R,x);
}
int searchPLACE(int k,int x){ //查询排在x的数是几
if(!k) return 0;
if(x<=T[L].siz) return searchPLACE(L,x);
x-=T[L].siz;
if(x<=T[k].ct) return T[k].val;
x-=T[k].ct;
return searchPLACE(R,x);
}
void pre(int k,int val){ //前驱,dist记录位置
if(!k) return;
if(val<=T[k].val) pre(L,val);
else dist=k,pre(R,val);
}
void ahe(int k,int val){ //后继
if(!k) return;
if(val>=T[k].val) ahe(R,val);
else dist=k,ahe(L,val);
}
①当S1中的所有元素小于S2(比如S1和S2是刚刚分裂出来的)时,只需要把S1最大的点伸展到根,然后连边即可。
②当S1和S2大小任意时,启发式合并,把小的往大的身上挪。
分裂:(以k为界限,左边小于或等于k,右边大于或等于k)
#include<bits/stdc++.h>
#define L T[k].son[0]
#define R T[k].son[1]
#define MAXN 100005
using namespace std;
int read(){
char c;int x=0,y=1;while(c=getchar(),(c<'0'||c>'9')&&c!='-');if(c=='-') y=-1;else x=c-'0';
while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x*y;
}
int root,dist,sz,n;
struct node{
int fa,siz,ct,val,son[2];
}T[MAXN];
void clear(int k){
T[k].siz=T[k].ct=T[k].fa=T[k].val=T[k].son[0]=T[k].son[1]=0;
}
void up(int k){
T[k].siz=T[L].siz+T[R].siz+T[k].ct;
}
int get(int k){
return T[T[k].fa].son[1]==k;
}
void rotate(int &k){
int fa=T[k].fa,gran=T[fa].fa;
int d1=get(k),d2=get(fa);
T[T[k].son[d1^1]].fa=fa;
T[fa].son[d1]=T[k].son[d1^1];T[k].son[d1^1]=fa;
T[k].fa=gran;T[fa].fa=k;
if(gran) T[gran].son[d2]=k;;
up(fa);up(k);
}
void splay(int k){
for(int fa;fa=T[k].fa;rotate(k))
if(T[fa].fa) rotate(get(fa)==get(k)?fa:k);
root=k;
}
void insert(int &k,int val,int pos){
if(!k){
k=++sz;
T[k].ct=T[k].siz=1;T[k].fa=pos;T[k].son[0]=T[k].son[1]=0;T[k].val=val;
dist=k;return;
}
if(val==T[k].val){
dist=k;T[k].siz++;T[k].ct++;return;
}
if(val<T[k].val) insert(T[k].son[0],val,k);
if(val>T[k].val) insert(T[k].son[1],val,k);
up(k);
}
int searchRANK(int k,int x){
if(!k) return 0;
if(x<T[k].val) return searchRANK(L,x);
if(x==T[k].val) return T[L].siz+1;
if(x>T[k].val) return T[L].siz+T[k].ct+searchRANK(R,x);
}
int searchPLACE(int k,int x){
if(!k) return 0;
if(x<=T[L].siz) return searchPLACE(L,x);
x-=T[L].siz;
if(x<=T[k].ct) return T[k].val;
x-=T[k].ct;
return searchPLACE(R,x);
}
void pre(int k,int val){
if(!k) return;
if(val<=T[k].val) pre(L,val);
else dist=k,pre(R,val);
}
void ahe(int k,int val){
if(!k) return;
if(val>=T[k].val) ahe(R,val);
else dist=k,ahe(L,val);
}
int find(int k,int val){
if(!k) return 0;
if(val==T[k].val){
splay(k);return k;
}
return find(T[k].son[val>T[k].val],val);
}
void delet(int x){
int pl=find(root,x);
if(!pl) return;
if(T[root].ct>1){
T[root].ct--,T[root].siz--;return;
}
if(!T[root].son[1]&&!T[root].son[0]){
clear(root),root=0;return;
}
if(!T[root].son[1]||!T[root].son[0]){
int rt=root;
root=T[root].son[0]+T[root].son[1];
T[root].fa=0;clear(rt);return;
}
int rt=root;
pre(root,x);splay(dist);
T[T[rt].son[1]].fa=root;T[root].son[1]=T[rt].son[1];
clear(rt);up(root);T[root].fa=0;
return;
}
int main()
{
n=read();
for(int i=1;i<=n;i++){
int x=read(),y=read();
if(x==1) insert(root,y,0),splay(dist);
if(x==2) delet(y);
if(x==3) printf("%d\n",searchRANK(root,y));
if(x==4) printf("%d\n",searchPLACE(root,y));
if(x==5) dist=0,pre(root,y),printf("%d\n",T[dist].val);
if(x==6) dist=0,ahe(root,y),printf("%d\n",T[dist].val);
}
return 0;
}
文献资料:图片转自博客ZigZagK,感谢ZZK大佬
文章浏览阅读680次,点赞5次,收藏23次。一,html+css基础1-1 Html和CSS的关系学习web前端开发基础技术需要掌握:HTML、CSS、JavaScript语言。下面我们就来了解下这三门技术都是用来实现什么的:HTML是网页内容的载体。内容就是网页制作者放在页面上想要让用户浏览的信息,可以包含文字、图片、视频等。CSS样式是表现。就像网页的外衣。比如,标题字体、颜色变化,或为标题加入背景图片、边框等。所有这些用来改变内容外观的东西称之为表现。JavaScript是用来实现网页上的特效效果。如:鼠标滑过弹出下拉菜单。或鼠_下列是html和css中的注释语句是
文章浏览阅读3.6k次。18.1 ARM设备树简介设备舒适一种描述印鉴的数据结构,它起源于OpenFirmware(OF) 采用设备树前后对比: 采用设备树之前:ARM架构的板极硬件细节过多的被硬编码在arch/arm/plat-xxx和arch/arm/mach-xxx中采用设备树之后:许多硬件细节可以直接通过它传递给Linux,而不再需要在讷河中进行大量的冗余编码设备树的组成:由一系列被命名的节点(Node)_第18章 arm linux设备树
文章浏览阅读2.9w次。(1)QDateTime 做差值 QDateTime beginTime = QDateTime::currentDateTime(); QDateTime endTime = QDateTime::currentDateTime(); QString value = QDateTime::fromMSecsSinceEpoch(endTime.toMSecsSince..._qt qdate转qjsovalue
文章浏览阅读1.9k次。当我想要在python上测试FeatureDetector并使用OpenCV的SIFT时,由于我在pycharm上仅仅安装了opencv-python,所以会出现报错(忘记截图了,好像是:‘module’ object has no attribute ‘xfeatures2d’。大致意思是说找不到 xfeatures2d 的库)。2018.9.30更新:Windows环境下把opencv中pyt..._为什么我下的python最后一步测试的时候
文章浏览阅读637次。认识微服务单体架构单体架构:将业务的所有功能集中在一个项目中开发,打成一个包部署。优点:架构简单,部署成本低缺点:耦合度高(维护困难、升级困难)分布式架构分布式架构:根据业务功能对系统做拆分,每个业务功能模块作为独立项目开发,称为一个服务。优点:降低服务耦合,有利于服务升级和拓展缺点:服务调用关系错综复杂分布式架构虽然降低了服务耦合,但是服务拆分时也有很多问题需要思考:服务拆分的粒度如何界定? 服务之间如何调用? 服务的调用关系如何管理?人们需要制定.._originaluri.gethost() 为 null
文章浏览阅读2.8k次,点赞5次,收藏44次。目录概念前言WEB应用程序动态WEB的访问过程WEB服务器技术讲解Tomcat安装tomcat配置发布一个WEB网站HTTP什么是HTTPHTTP的两个时代HTTP请求HTTP请求MavenMaven项目架构管理工具在IDEA里面使用Maven创建一个普通的Maven项目标记文件夹功能解决遇到的问题Servlet简介HelloServletMaven环境优化Servlet原理概念前言静态Web:. 提供给所有人看数据不会发生变化!. HTML,CSS动态Web:.有数据交互,登录账号密码,网站_狂神说javaweb笔记
文章浏览阅读2.5k次,点赞4次,收藏6次。本节目标1.掌握如何解决my.ini配置文件修改后无法启动的问题net stop mysql80配置文件my.ini的默认路径C:\ProgramData\MySQL\MySQL Server 8.0防止出错,拷贝一份复制到桌面,另存为的方式要保存为ANSInet start mysql80解决问题..._my.ini替换后无法启动
文章浏览阅读632次。学习窗口看门狗记录_如果在while(1)循环体一直重设窗口看门狗值,系统会不会复位
文章浏览阅读5.1k次,点赞19次,收藏83次。因为有小伙伴刚好问到这个问题,松哥就抽空撸一篇文章和大家聊聊这个话题。加密解密本身并不是难事,问题是在何时去处理?定义一个过滤器,将请求和响应分别拦截下来进行处理也是一个办法,这种方式虽然粗暴,但是灵活,因为可以拿到一手的请求参数和响应数据。不过 SpringMVC 中给我们提供了 ResponseBodyAdvice 和 RequestBodyAdvice,利用这两个工具可以对请求和响应进行预处理,非常方便。所以今天这篇文章有两个目的:分享参数/响应加解密的思路。分享 ResponseBodyA_encrypt-body-spring-boot-starter
文章浏览阅读2.4k次。1、微软雅黑是 Vista 及更高版本 Windows 的标配中文字体,但不是 XP 的标配字体,XP 的任何一个 SP 或更新包都没有包含它。2、XP系统默认中文字体是宋体,在电脑上的显示效果不如微软雅黑好看。3、程序如果在XP下使用微软雅黑,但系统又没有该字体时,会使用XP默认字体。4、XP 系统上的微软雅黑字体,通常有两种来源:用户主动下载安装或安装 Of_xp默认字体变成微软雅黑了
文章浏览阅读788次。学习笔记之MVVM+RAC公司项目之前的很多年一直是用MVC框架,最近项目改版(加重构)提出了使用MVVM + RAC的框架结构,以达到各个部分模块代码之间的解耦。关于MVVM 以及RAC 还不太了解的同学请自行百度,我这里主要讲解下简单的使用。 以登录界面为例,需求如下: - 注册用户输入手机号密码登录 - 手机号获取验证码快速登录 - 游客登录 - 第三方(QQ,微信…)登录_ioss中mvvm使用raccommand请求多个接口
文章浏览阅读4.5k次,点赞6次,收藏19次。【笔记】度相关、不相关网络的理解(不一定正确)社交网络中,你刚注册,系统给你推荐了小明,你关注小明的概率和小明一点关系都没有,纯粹是你为了完成任务随便选了个人关注。因为你关注小明的概率随机,只是由你自己的关注总数(节点出度)决定,和对方的关注数和被关注数无关。这个网络就是度不相关网络。你已经玩社交网络很久,系统根据你的兴趣给你推荐小明,你关注小明的概率和小明是不是大V有很大关系(假设..._uncorrelated network