太原网站建设总部地址,毕业设计网站设计说明书,郑州市广告牌制作,做影视网站侵权不Splay 简介
Splay#xff08;伸展树#xff09;#xff0c;又叫做分裂树#xff0c;是一种自调整形式的二叉查找树#xff0c;满足二叉查找树的性质#xff1a;一个节点左子树的所有节点的权值#xff0c;均小于这个节点的权值。且其右子树所有节点的权值#xff0c;均…Splay 简介
Splay伸展树又叫做分裂树是一种自调整形式的二叉查找树满足二叉查找树的性质一个节点左子树的所有节点的权值均小于这个节点的权值。且其右子树所有节点的权值均大于这个节点的权值。 因此Splay的中序遍历是一个递增序列。
Splay可以用来维护实链剖分LCT等作为普通平衡树它的优势在于不需要记录用于平衡树的冗余信息。
Splay维护一个有序集合支持如下操作
向集合中添加一个数删除集合中的一个数求出一个数的排名根据排名求出这个数查找一个数的前驱查找一个数的后继
Splay原理以及实现
模板题
约定
为了代码简洁以及安全我们用数组模拟Splay并且做出规定如下性质
安全性不在Splay上的节点以及被删除的节点其所有信息应该被清空。保证我们保证函数不可能被非法调用或者所有可能的非法调用是无害的因此不需要在被调用的函数内部进行特判。 例如我们保证get(u)中u一定有父亲。 例如push_up(0)是无害的。代码重用我们尽可能的保证代码重用节点从1开始编号0号节点可能有多余的子孙/后代信息但是其val,cnt,siz信息始终为0。
或许每一个约定都并不是完全必要的。
节点node
Splay上的一个节点(node)维护这样几个信息
fa这个节点的父亲编号fa0表示没有父亲ch[0]节点的左儿子编号ch[0]的别名是l若l0表示没有左儿子ch[1]节点的右儿子编号ch[1]的别名是r若r0表示没有右儿子val节点的权值cnt节点权值在集合中出现的次数siz以此节点为根的子树的大小成员函数set(v,c,s)用来初始化节点信息使得valv,cntc,sizs并且让falr0。其中c和s的默认值为1
const int N2e6;
struct node {int fa,ch[2],val,cnt,siz;intlch[0],rch[1];void set(int v,int c1,int s1) {falr0;valv;cntc;sizs;}
} t[N5];
int tot,root;左右儿子函数get
函数原型
bool get(int);函数get(u)返回编号为u的节点是其父亲的左儿子返回0或者右儿子返回1保证传入的参数u一定有父亲。
函数定义
bool get(int u) {return t[t[u].fa].ru;
}上传push_up
函数原型
void push_up(int);函数push_up(u)将编号为u节点用自己的两个儿子的信息更新自己的siz信息。当有儿子编号为0时不影响因为我们保证0号节点的siz信息为0。
函数定义
void push_up(int u) {t[u].sizt[t[u].l].sizt[t[u].r].sizt[u].cnt;
}事实上push_up(0)也不影响0节点的siz因为调用push_up(0)仅在pop函数中root0时但此时由于早已del了0节点的左右儿子因此0节点必然没有左右儿子的信息。
加入节点add
函数原型
void add(int,int,bool);函数add(fa,son,k)将编号为son的节点加入Splay并且它是父亲fa的k侧儿子。
函数定义
void add(int fa,int son,bool k) {t[t[son].fafa].ch[k]son;
}删除节点del
函数原型
void del(int);函数del(u)将编号为u的节点从Splay中删除这需要操作它的父亲和左右儿子并且将它的三个权值val,cnt,siz清空。
函数定义
void del(int u) {t[t[u].l].fat[t[u].r].fat[t[u].fa].ch[get(u)]0;t[u].set(0,0,0);
}旋转rotate
Splay的单次操作复杂度并不是严格 O ( log n ) O(\log n) O(logn)的但是Splay依靠其伸展操作(splay)使得总复杂度为均摊 O ( n log n ) O(n\log n) O(nlogn)而不是期望 O ( n log n ) O(n\log n) O(nlogn)的。 在伸展树上的一般操作都基于伸展操作假设想要对一个二叉查找树执行一系列的查找操作为了使整个查找时间更小被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法 在每次查找之后对树进行重构把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树它会沿着从某个节点到树根之间的路径通过一系列的旋转把这个节点搬移到树根去。 函数原型
void rotate(int);当树是完全二叉树时单次查询复杂度为 O ( log n ) O(\log n) O(logn) 当树是一条链时单次查询复杂度为 O ( n ) O(n) O(n) rotate通过改变树的形态达到使得Splay的均摊复杂度为 O ( log n ) O(\log n) O(logn)的目的。
函数rotate(u)将编号为u的节点旋转一次。
旋转原理
首先我们需要记录一个变量k
kget(u)
这表明了编号为u的节点是其父亲的哪侧儿子k0表示左儿子k1表示右儿子。
旋转过程需要保存几个节点编号
u当前节点fa当且节点的父亲son节点t[u]的异侧儿子即sont[u].ch[k^1]。例如如果t[u]是t[fa]的左儿子那么t[son]就是t[u]的右儿子。ffa当前节点的父亲的父亲。
画出一个图来示意一下 在这里t[fa]是t[ffa]的哪侧儿子无关紧要。
接下来我们修改树的形态完成三步操作
用u顶替掉原来fa的位置 把u设置为ffa的儿子fa是哪侧儿子u就是哪侧儿子。用fa顶替掉原来son的位置fa变成u的k^1儿子把son设为fa的同侧儿子替代uson变成fa的k儿子
还是看代码比较好懂
int kget(u),sont[u].ch[k^1],fat[u].fa,ffat[fa].fa;
add(ffa,u,get(fa));
add(u,fa,k^1);
add(fa,son,k);画个图
直接背下来写得比较快。
旋转实现
完整代码是这样的
void rotate(int u) {int kget(u),sont[u].ch[k^1],fat[u].fa,ffat[fa].fa;add(ffa,u,get(fa));add(u,fa,k^1);add(fa,son,k);push_up(fa);push_up(u);
}注意最后要更新节点信息。先push_up父亲再push_up自身因为此时原来的父亲是自身的儿子。
保证编号为u的节点存在父亲。 事实上可能会有son0或ffa0使得编号为0的节点可能携带有额外的祖先/后代信息但是这不影响。
其实我们还可以选择把子孙转成指定祖先的儿子处就停止这里不多说了。
伸展splay
函数原型
int splay(int);伸展操作是执行若干次旋转操作把编号为u的节点旋转到根并返回u的编号。
执行的方法是这样的
记录当且节点的编号u更新它目前的父亲编号fat[u].fa注意u的父亲是不断变化的因此要更新
如果u没有父亲说明u是根节点停止如果fa不存在父亲说明u再旋转一次就会旋转到根rotete(u)get(fa)get(u)说明u和fa是同侧儿子先旋转fa再旋转urotate(fa),rotate(u)get(fa)!get(u)说明u和fa是异侧儿子旋转两次urotate(u),rotate(u)
写成代码是这样的
int splay(int u) {for(int fa; (fat[u].fa); rotate(u))if(t[fa].fa)rotate(get(u)get(fa)?fa:u);return rootu;
}注意最后把根节点编号设为u。
伸展主要有三个作用
可以保证时间复杂度rotate内有push_up函数如果修改了u的信息伸展一下可以更新到根节点的链上信息把u旋转到根便于下一步操作
加入值push
函数原型
int push(int);函数push(val)将val在集合中出现的次数增加1并返回val所在的节点编号如果val在集合中原来并不存在就创建一个新节点。
函数分为三种情况讨论
Splay为空直接新建一个节点然后把根设为这个节点。Splay中以前存在val这个值找到存储这个值的节点先把它旋转到根然后把它的cnt增加1再push_up以更新信息。 因为此时这个节点已经是根了对它调用splay不会rotate因此必须手动psuh_up。 即使我们先前不把这个节点旋转到根但是这个节点可能原本就是根还是需要更新一下siz信息Splay中不存在val这个值找到一个合适的叶子节点然后对val新建一个节点并且把新节点的父亲设为这个叶子节点。把这个节点旋转到根。
为了保证时间复杂度同时为了更新链上记录的siz信息最后都要把val所在的节点旋转到根。
函数定义
int push(int val) {if(!root) {t[tot].set(val);return roottot;}int xval_find(val);这里的val_find函数很特殊如果找到val会返回这个节点作为根节点否则会返回一个可以作为新节点父亲的叶子节点if(t[x].valval) {t[x].cnt;push_up(x);return x;}t[tot].set(val);要先set再加边否则set会将t[tot]上存储的祖先/子孙信息清除add(x,tot,t[x].valval);return splay(tot);
}删去值pop
函数原型
void pop(int);函数pop(val)将集合中val出现的次数减1保证val之前至少出现过一次。
函数分几种情况讨论 首先找到val所在的节点的编号设为u然后把这个节点旋转到根。
如果t[u].cnt1直接让cnt--如果u至少没有一个儿子那就把根设为它的另一个儿子然后删除u。 如果u没有任何一个儿子是不影响的。否则说明u既有左儿子又有右儿子也就是说val既有前驱又有后继 因此找到val的前驱把前驱旋转到根此时u一定是根的右儿子而且由于根是前驱所以u没有左儿子因此直接把u的右儿子设为根的右儿子然后删除u即可。
注意最后要push_up(root)因为第1,3种情况下需要更新根节点信息。
函数实现
void pop(int val) {int uval_find(val);if(t[u].cnt1) t[u].cnt--;else if(!t[u].l||!t[u].r) roott[u].l|t[u].r,del(u);else {pre(val);int rt[u].r;del(u);这里要先清除u再连边。否则清除u时会顺便擦除根节点和r节点的祖先关系信息add(root,r,1);此时前驱是根节点把u的右儿子设为其前驱的右儿子}push_up(root);
}用值查找val_find
函数原型
int val_find(int);函数val_find(val)在集合中查找值val如果它出现过那就把val所在的节点旋转到根并且返回它的编号如果它没有出现过那就返回一个可以作为val父亲的叶子节点编号。 如果此时树为空函数会返回0尽管不会出现这样的调用
主要做法就是从根节点开始找如果找到了就返回没找到就按照大小关系继续往下走。 如果找到叶子节点还没找到val就返回它的父亲。
函数定义
int val_find(int val) {int uroot,fa0;while(u)if(t[fau].valval) return splay(u);else ut[u].ch[t[u].valval];return fa;
}用排名查找rank_find
函数原型
int rank_find(int,int);函数rank_find(u,rank)查找u子树内排名为rank的节点并返回节点编号。注意这里是子树内排名而不是全局排名。
我们通常调用时参数uroot即查询全局排名。 把rank_find函数设计为两个参数一方面是为了方便递归调用另一方面不为其提供一个参数的重载版本是为了防止将其与val_find函数与find_rank函数混淆。
rank_find(u,rank)函数这样设计 分情况讨论
如果rank左子树大小递归到左儿子rank_find(t[u].l,rank)否则如果rank左子树大小自身节点的cnt递归到右儿子rank_find(t[u].r,rank-t[t[u].l].siz-t[u].cnt)否则旋转并且返回自身节点编号
这种独特的递归顺序使得如果查询的rank大于子树之内的最大排名会返回子树最大值的节点编号避免了进一部的分情况讨论。
函数定义
int rank_find(int u,int rank) {int lt[t[u].l].siz;这样可以少打很多字if(rankl) return rank_find(t[u].l,rank);else if(ranklt[u].cnt) return rank_find(t[u].r,rank-l-t[u].cnt);return splay(u);
}查询值的排名find_rank
函数原型
int find_rank(int);函数find_rank(val)查询值val的排名不保证val出现过。 没有提供查询节点排名的函数是因为节点不存在排名如果想要查询节点u对应的权值的排名可以调用find_rank(t[u].val)。
查询val的排名可以通过把val加入集合一次然后把它对应的节点旋转到根。那么val的排名就是它对应节点的左子树的大小1。 然后再把val在集合中删去一次。
函数定义
int find_rank(int val) {int anst[t[push(val)].l].siz1;pop(val);return ans;
}查找前驱/后继bound
函数原型
int bound(int,bool);函数bound(val,k)用于查询前驱/后继旋转节点到根并返回对应的节点编号。 函数bound(val,0)用于查询值val的前驱。 函数bound(val,1)用于查询值val的后继。
bound原理
这里以查询前驱举例 查询val前驱的方法就是无论Splay中是否存在val我们都先push(val)这样Splay内肯定存在val且为Splay的根。 走到根的左儿子上然后不断地走右儿子直到走到叶子节点即为前驱记录答案后pop(val)。
查询后继的方法是类似的先push(val)走到根的右儿子上然后不断地走左儿子叶子节点即为前驱记录答案后pop(val)。
注意到可以把这两种情况合并起来设k0表示查询前驱k1表示查询后继则函数定义如下
int bound(int val,bool k) {int ut[push(val)].ch[k];while(t[u].ch[k^1]) ut[u].ch[k^1];pop(val);return splay(u);
}前驱pre
函数原型
int pre(int);pre为查询前驱提供了专门的接口。 函数pre(val)表示查询val的前驱把前驱旋转到根并且返回前驱编号。
val可以比集合中的任何数都要大但是不能没有前驱否则运行可能出现问题我们没有保证splay(0)不会出错因为我们没有保证t[0]不携带非零的祖先后代信息。
如果非要这样查询可能没有前驱/后继的数的话可以设置哨兵push(-INF),push(INF)
函数定义
int pre(int val) {return bound(val,0);
}后继nxt
函数原型
int nxt(int);函数nxt(val)表示查询val的后继把后继旋转到根并返回后继编号。 必须要保证val有后继。
函数定义
int nxt(int val) {return bound(val,1);
}完整代码
空间复杂度
注意到Splay的任意一种操作至多创建一个节点因此空间复杂度为一倍操作次数。本题要算上一开始的 1 0 5 10^5 105次操作
代码
#includeiostream
using namespace std;
const int N2e6;
struct node {int fa,ch[2];int val,cnt,siz;int lch[0],rch[1];void set(int v,int c1,int s1) {lrfa;valv;cntc;sizs;}
}t[1100005];
int tot,root;
bool get(int);
void push_up(int);
void add(int,int,bool);
void del(int);
void rotate(int);
int splay(int);
int push(int);
void pop(int);
int val_find(int);
int rank_find(int,int);
int find_rank(int);
int bound(int,bool);
int pre(int);
int nxt(int);
int a[N5];
int main() {int n,m;cinnm;for(int i1;in;i) cina[i];for(int i1;in;i) push(a[i]);int ans0,last0;while(m--) {int op,x;cinopx;
// if(op1) push(x);
// if(op2) pop(x);
// if(op3) coutfind_rank(x)endl;
// if(op4) coutt[rank_find(root,x)].valendl;
// if(op5) coutt[pre(x)].valendl;
// if(op6) coutt[nxt(x)].valendl;x^last;if(op1) push(x);if(op2) pop(x);if(op3) ans^(lastfind_rank(x));if(op4) ans^(lastt[rank_find(root,x)].val);if(op5) ans^(lastt[pre(x)].val);if(op6) ans^(lastt[nxt(x)].val);}coutans;
}
bool get(int u) {return t[t[u].fa].ru;
}
void push_up(int u) {t[u].sizt[t[u].l].sizt[t[u].r].sizt[u].cnt;
}
void add(int fa,int son,bool k) {t[t[son].fafa].ch[k]son;
}
void del(int u) {t[t[u].l].fat[t[u].r].fat[t[u].fa].ch[get(u)]0;t[u].set(0,0,0);
}
void rotate(int u) {int kget(u),sont[u].ch[k^1],fat[u].fa,ffat[fa].fa;add(ffa,u,get(fa));add(u,fa,k^1);add(fa,son,k);push_up(fa);push_up(u);
}
int splay(int u) {for(int fa;(fat[u].fa);rotate(u)) if(t[fa].fa)rotate(get(fa)get(u)?fa:u);return rootu;
}
int push(int val) {if(!root) {t[tot].set(val);return roottot;}int xval_find(val) ;if(t[x].valval) {t[x].cnt;push_up(x);return x;}t[tot].set(val);add(x,tot,t[x].valval);return splay(tot);
}
void pop(int val) {int uval_find(val);if(t[u].cnt1) t[u].cnt--;else if(!t[u].l||!t[u].r) roott[u].l|t[u].r,del(u);else {pre(val);int rt[u].r;del(u);add(root,r,1);}push_up(root);
}
int val_find(int val) {int uroot,fa0;while(u) if(t[fau].valval) return splay(u);else ut[u].ch[t[u].valval];return fa;
}
int rank_find(int u,int rank) {int lt[t[u].l].siz;if(rankl) return rank_find(t[u].l,rank);else if(rankt[u].cntl) return rank_find(t[u].r,rank-t[u].cnt-l);return splay(u);
}
int find_rank(int val) {int anst[t[push(val)].l].siz1;pop(val);return ans;
}
int bound(int val,bool k) {int ut[push(val)].ch[k];while(t[u].ch[k^1]) ut[u].ch[k^1];pop(val);return splay(u);
}
int pre(int val) {return bound(val,0);
}
int nxt(int val) {return bound(val,1);
}后话
关于pop和pre
有一种观点认为对pre函数查询不在集合里面的val会导致创建新节点而删除val时又有可能导致查询val的前驱这可能会导致循环调用。
但是这种说法是错误的因为事实上如果在pop(val)时调用pre(val)进而导致了一次push(val)后再pop(val)此时val对应节点的cnt至少为2了所以在本层pop(val)不会调用pre(val)而是会将cnt--。
后记
于是皆大欢喜。
