首页 > 其他分享 >关于指针Splay

关于指针Splay

时间：2023-02-15 19:15:55浏览次数：48  
标签：return cur val int Splay fa lson 关于 指针

关于指针Splay

目录

更好的阅读体验戳此进入

写在前面

大概就是写完序列之后很久的今天突然发现序列还有个加强版，加强版数据不随机 ODT 就过不去了，要么需要用一些 可持久化ODT 这种奇怪的东西在复杂度正确的情况下通过，要么就是要用到 可持久化平衡树 这种科技，于是考虑直接把平衡树相关知识补一补。

当然可能只是大概写一下，仅保证我自己复习时能看懂。

并且，对于这种相对易于适配指针，或者本质上就是基于指针的，我们当然也会考虑通过指针实现。

操作核心

Splay 区别于 Treap，Treap 时是通过随机值以使得期望复杂度在 $ O(n \log n) $，Splay 则是通过旋转保证层高在 $ O(\log n) $ 而保证复杂度。

然后关于具体的证明大概是需要一些基于势能分析的高妙证明，显然我不会，所以总之就记住，在所有操作所有过程中，只要进行了对某个点的查询等，就将其 Splay 到根即可。

节点

考虑一个节点，大致需要维护三个指针，即对于父亲，左儿子和右儿子。并且还需要维护一个 $ siz $ 表示子树大小，以及 $ cnt $ 表示该权值的节点数量。这个东西的用处后面会说到。

同时指针版有一个细节，一般数组版直接访问 $ 0 $ 下标即可获得 $ siz = 0 $，但对于指针版我们需要判断是否为 $ \texttt{nullptr} $，是的话 $ siz = 0 $。

#define siz(p) (p ? p->siz : 0)
#define son(p, dir) ((dir) ? p->rson : p->lson)

struct Node{
    Node* lson;
    Node* rson;
    Node* fa;
    int cnt;
    int siz;
    int val;
    OPNEW;
}nd[110000];
ROPNEW(nd);
Node* root;

Update

更新一个点的 $ siz $。

void Update(Node* p){
    p->siz = p->cnt + siz(p->lson) + siz(p->rson);
}

GetDir

判断 $ p $ 是 $ fa_p $ 的左儿子还是右儿子，用处后面会说。

bool GetDir(Node* p){
    return p->fa ? p->fa->rson == p : false;
}

Rotate

对于旋转操作，考虑一对父子关系 $ x $ 和 $ fa_x $，若 $ x $ 是 $ fa_x $ 的左儿子，那么旋转后 $ fa_x $ 应为 $ x $ 的右儿子，而 $ x $ 本身的右儿子会因为 BST 性质变为 $ fa_x $ 的左儿子。对于右儿子关系的旋转同理。

void Link(Node* p, Node* fa, bool dir){
    if(fa)son(fa, dir) = p, Update(fa);
    if(p)p->fa = fa;
}
void Rotate(Node* p){
    auto fa = p->fa, gfa = fa->fa;
    auto dir1 = GetDir(p), dir2 = GetDir(fa);
    Link(son(p, !dir1), fa, dir1), Link(fa, p, !dir1), Link(p, gfa, dir2);
}

Splay

这个东西比较高妙，本质上就是进行双旋，即为了保证层高，考虑节点 $ p $ 和其父亲和祖父，若三点共线，即两个左儿子关系或两个右儿子关系，那么需要先旋转父亲，再旋转 $ p $。反之则直接旋转两次。

如果不按照这个方式，层高将无法保证，具体原因不再赘述。

具体来说，我们要从 $ p $ 一直旋转到根，每次判断 $ p $ 和 $ p $ 的父亲与祖父的位置关系即可。最终根节点应变为 $ p $。

void Splay(Node* p){
    if(!p)return;
    while(p->fa != npt){
        if(p->fa->fa != npt)
            Rotate(GetDir(p) == GetDir(p->fa) ? p->fa : p);
        Rotate(p);
    }root = p;
}

然后关键操作就结束了，剩下的就是一些操作的实现。

Insert

没什么可说的，正常维护即可。

void Insert(int val, Node* cur = root, Node* fa = npt){
    if(cur && val != cur->val)return Insert(val, val > cur->val ? cur->rson : cur->lson, cur);
    if(!cur){
        cur = new Node{npt, npt, fa, 1, 1, val};
        if(fa)son(fa, val > fa->val ? true : false) = cur;
    }else ++cur->cnt;
    Splay(cur);
}

Find

查找某个元素的位置，同时需要将该元素 Splay 到根。

Node* Find(int val, Node* cur = root, Node* fa = npt){
    if(!cur)return Splay(fa), fa;
    if(cur->val != val)return Find(val, val > cur->val ? cur->rson : cur->lson, cur);
    return Splay(cur), cur;
}

需要注意一个细节，若查找不到该元素，应该返回的是接近该元素的数，以便于找前驱后继时的处理。

Delete

删除某个元素，首先查找该元素，同时也就将会自动将该元素 Splay 到根，此时考虑若 $ cnt \gt 1 $ 那么直接 $ cnt \leftarrow cnt - 1 $ 即可，注意 $ siz $ 同时需要更新，但因在根节点所以无需更新祖先 $ siz $。

若将该元素删没了，则需要考虑，若左右子树均无节点，那么树空。反之考虑若仅右子树右节点，那么直接将根的右儿子作为根并丢弃原来的根即可。在以上所有情况之外则应考虑，在左儿子中找到最大的值，即左儿子的右链末， Splay 其作为根，此时便可将原来根的右子树接到新根的右子树，并删除新根的父亲关系即可。

void Delete(int val){
    auto cur = Find(val);
    if(!cur)return;
    if(cur->cnt > 1)return --cur->cnt, --cur->siz, void();
    if(!cur->lson && !cur->rson)return root = npt, void();
    if(!cur->lson)return root = cur->rson, cur->rson->fa = npt, void();
    auto mxp = cur->lson;
    while(mxp->rson)mxp = mxp->rson;
    Splay(mxp);
    Link(cur->rson, root, true), Link(root, npt, true);
}

FindRankByVal

从意义上考虑并简单维护一下即可。

int FindRankByVal(int val, Node* cur = root, int tot = siz(root->lson)){
    if(!cur || cur->val == val)return Splay(cur), tot + 1;
    return FindRankByVal(
        val,
        val < cur->val ? cur->lson : cur->rson,
        val < cur->val ? tot - siz(cur->lson) + (cur->lson ? siz(cur->lson->lson) : 0) : tot + cur->cnt + (cur->rson ? siz(cur->rson->lson) : 0)
    );
}

FindValByRank

同理，略。

int FindValByRank(int rnk, Node* cur = root, int tot = siz(root->lson)){
    if(!cur)return -1;
    if(tot + 1 <= rnk && rnk <= tot + cur->cnt)return Splay(cur), cur->val;
    return FindValByRank(
        rnk,
        rnk < tot + 1 ? cur->lson : cur->rson,
        rnk < tot + 1 ? tot - siz(cur->lson) + (cur->lson ? siz(cur->lson->lson) : 0) : tot + cur->cnt + (cur->rson ? siz(cur->rson->lson) : 0)
    );
}

FindPre

直接查找该元素，若返回值已满足前驱则直接返回，反之从左儿子中找到右链末，即左儿子中最大的即可。

int FindPre(int val){
    auto cur = Find(val);
    if(cur->val < val)return Splay(cur), cur->val;
    cur = cur->lson;
    while(cur->rson)cur = cur->rson;
    return Splay(cur), cur->val;
}

FindNxt

对应前者反过来即可。

int FindNxt(int val){
    auto cur = Find(val);
    if(cur->val > val)return Splay(cur), cur->val;
    cur = cur->rson;
    while(cur->lson)cur = cur->lson;
    return Splay(cur), cur->val;
}

Code

最终程序。

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Node::operator new(size_t){static Node* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define siz(p) (p ? p->siz : 0)
#define son(p, dir) ((dir) ? p->rson : p->lson)

template < typename T = int >
inline T read(void);

struct Node{
    Node* lson;
    Node* rson;
    Node* fa;
    int cnt;
    int siz;
    int val;
    OPNEW;
}nd[110000];
ROPNEW(nd);
Node* root;

void Update(Node* p){
    p->siz = p->cnt + siz(p->lson) + siz(p->rson);
}
bool GetDir(Node* p){
    return p->fa ? p->fa->rson == p : false;
}
void Link(Node* p, Node* fa, bool dir){
    if(fa)son(fa, dir) = p, Update(fa);
    if(p)p->fa = fa;
}
void Rotate(Node* p){
    auto fa = p->fa, gfa = fa->fa;
    auto dir1 = GetDir(p), dir2 = GetDir(fa);
    Link(son(p, !dir1), fa, dir1), Link(fa, p, !dir1), Link(p, gfa, dir2);
}
void Splay(Node* p){
    if(!p)return;
    while(p->fa != npt){
        if(p->fa->fa != npt)
            Rotate(GetDir(p) == GetDir(p->fa) ? p->fa : p);
        Rotate(p);
    }root = p;
}
void Insert(int val, Node* cur = root, Node* fa = npt){
    if(cur && val != cur->val)return Insert(val, val > cur->val ? cur->rson : cur->lson, cur);
    if(!cur){
        cur = new Node{npt, npt, fa, 1, 1, val};
        if(fa)son(fa, val > fa->val ? true : false) = cur;
    }else ++cur->cnt;
    Splay(cur);
}
Node* Find(int val, Node* cur = root, Node* fa = npt){
    if(!cur)return Splay(fa), fa;
    if(cur->val != val)return Find(val, val > cur->val ? cur->rson : cur->lson, cur);
    return Splay(cur), cur;
}
void Delete(int val){
    auto cur = Find(val);
    if(!cur)return;
    if(cur->cnt > 1)return --cur->cnt, --cur->siz, void();
    if(!cur->lson && !cur->rson)return root = npt, void();
    if(!cur->lson)return root = cur->rson, cur->rson->fa = npt, void();
    auto mxp = cur->lson;
    while(mxp->rson)mxp = mxp->rson;
    Splay(mxp);
    Link(cur->rson, root, true), Link(root, npt, true);
}
int FindRankByVal(int val, Node* cur = root, int tot = siz(root->lson)){
    if(!cur || cur->val == val)return Splay(cur), tot + 1;
    return FindRankByVal(
        val,
        val < cur->val ? cur->lson : cur->rson,
        val < cur->val ? tot - siz(cur->lson) + (cur->lson ? siz(cur->lson->lson) : 0) : tot + cur->cnt + (cur->rson ? siz(cur->rson->lson) : 0)
    );
}
int FindValByRank(int rnk, Node* cur = root, int tot = siz(root->lson)){
    if(!cur)return -1;
    if(tot + 1 <= rnk && rnk <= tot + cur->cnt)return Splay(cur), cur->val;
    return FindValByRank(
        rnk,
        rnk < tot + 1 ? cur->lson : cur->rson,
        rnk < tot + 1 ? tot - siz(cur->lson) + (cur->lson ? siz(cur->lson->lson) : 0) : tot + cur->cnt + (cur->rson ? siz(cur->rson->lson) : 0)
    );
}
int FindPre(int val){
    auto cur = Find(val);
    if(cur->val < val)return Splay(cur), cur->val;
    cur = cur->lson;
    while(cur->rson)cur = cur->rson;
    return Splay(cur), cur->val;
}
int FindNxt(int val){
    auto cur = Find(val);
    if(cur->val > val)return Splay(cur), cur->val;
    cur = cur->rson;
    while(cur->lson)cur = cur->lson;
    return Splay(cur), cur->val;
}

int main(){
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int N = read();
    while(N--){
        int opt = read();
        switch(opt){
            case 1:{Insert(read()); break;}
            case 2:{Delete(read()); break;}
            case 3:{printf("%d\n", FindRankByVal(read())); break;}
            case 4:{printf("%d\n", FindValByRank(read())); break;}
            case 5:{printf("%d\n", FindPre(read())); break;}
            case 6:{printf("%d\n", FindNxt(read())); break;}
        }
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

TODO: Splay维护序列待更新

TODO: LCT待更新

UPD

update-2023_01_10 初稿

标签：return,cur,val,int,Splay,fa,lson,关于,指针
From： https://www.cnblogs.com/tsawke/p/17124327.html

相关文章

  • c++学习7 指针与数组
    一二维数组与数组指针的关系二维数组名，代表的是第0行的行地址，“+1”是跳过一个行。而取“*”的话，则是在当前行地址基础上再取列地址，那么如果我们再取一个“*”呢？就会......
  • 企业微信关于自建应用获取的useId是密文
    出现的可能原因：返回的密文的话可能是跨企业 或者是消费的code不是在当前企业登入产生的。企业微信自建应用目前发现获取userid为密文的两种情况1.针对使用微信开发者......
  • 指针
    指针也就是内存地址，指针变量是用来存放内存地址的变量(1)指针变量的声明​ 指针类型声明的一般格式为：Type指针类型名=^类型;​ New过程创建一个新的动态变量，并把指......
  • springboot在test的时候，new的类报空指针
    ok@ComponentpublicclassFifthGithubCrawler{@AutowiredprivateKBComponentVersionRepositoryversionRepository;/***导出所有数据到json......
  • 关于activemq安装在linux后无法访问到的情况处理
    首先安装好之后要开启对应端口限制#firewall-cmd--zone=public--add-port=61616/tcp--permanent#firewall-cmd--zone=public--add-port=8161/tcp--permanent#......
  • Splay 板子
    OIwiki代码害人不浅。#include<bits/stdc++.h>#defineilinlineusingnamespacestd;ilintread(){ intxr=0,F=1;charcr=getchar(); while(cr<'0'||cr>'9')......
  • 关于Linux从内核启动选项中开启对ipv6的支持
    本文环境：RedHatEnterpriseLinuxrelease8.1(Ootpa)因为最近在一台服务器上安装Nginx后启动，发现有报错：nginx:[emerg]socket()[::]:80failed(97:Addressfamily......
  • c++函数指针
    函数的地址是存储其机器语言代码的内存的开始地址。通常，这些地址对用户而言，既不重要，也没有什么用处，但对程序而言，却很有用。例如，可以编写将另一个函数的地址作为参数的函数。......
  • Android Scroller完全解析，关于Scroller你所需知道的一切
    Scroller是一个专门用于处理滚动效果的工具类，可能在大多数情况下，我们直接使用Scroller的场景并不多，但是很多大家所熟知的控件在内部都是使用Scroller......
  • linux内核之指针打印函数
    linux内核打印函数：define_netdev_printk_level(netdev_info,KERN_INFO);netdev_info：输入形参，指针函数；实际使用方法： ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99