首页 > 其他分享 >平衡树模板

平衡树模板

时间：2023-09-27 19:22:24浏览次数：24  
标签：Node cur val int rch 模板 平衡 lch

Splay

#define lch ch[0]
#define rch ch[1]
class Splay{
    private:
        struct Node{
            int val,cnt,sz;
            Node *fa,*ch[2];
            inline void pushup(){
                sz=cnt;
                if(lch) sz+=lch->sz;
                if(rch) sz+=rch->sz;
            }
            inline bool checkson(){
                return this==fa->rch;
            }
            Node(){}
            Node(int x){
                val=x;cnt=1;sz=1;
                fa=lch=rch=nullptr;
            }
            Node(int x,Node *ptr){
                val=x;cnt=1;sz=1;
                fa=ptr;
                lch=rch=nullptr;
            }
        };
        Node *rt;
        inline void rotate(Node *x){
            assert(x);
            Node *y=x->fa,*z=y->fa;
            int dir=!x->checkson();
            y->ch[!dir]=x->ch[dir];
            if(x->ch[dir]) x->ch[dir]->fa=y;
            x->ch[dir]=y;

            y->fa=x;
            x->fa=z;
            if(z) z->ch[y==z->rch]=x;

            y->pushup();
            x->pushup(); 
        }
        inline void splay(Node *cur){
            assert(cur);
            if(cur==rt) return;
            Node *curfa;
            while(cur->fa){
                curfa=cur->fa;
                if(curfa->fa) rotate(cur->checkson()==curfa->checkson()?curfa:cur);
                rotate(cur);
            }
            rt=cur;
        }
        inline Node* getrtpre(){
            Node *cur=rt->lch;
            if(!cur) return cur;
            while(cur->rch) cur=cur->rch;
            splay(cur);
            return cur;
        }
        inline Node* getrtnxt(){
            Node *cur=rt->rch;
            if(!cur) return cur;
            while(cur->lch) cur=cur->lch;
            splay(cur);
            return cur;
        }
    public:
        inline void insert(int val){
            if(!rt){
                rt=new Node(val);
                return;
            }
            Node *cur=rt,*curfa=nullptr;
            while(true){
                assert(cur);
                if(cur->val==val){
                    cur->cnt++;
                    cur->pushup();
                    if(curfa) curfa->pushup();
                    splay(cur);
                    break;
                }
                curfa=cur;
                cur=cur->ch[cur->val<val];
                if(!cur){
                    curfa->ch[curfa->val<val]=new Node(val,curfa);
                    curfa->pushup();
                    splay(curfa->ch[curfa->val<val]);
                    break;
                }
            }
        }
        inline int query_val_rk(int val){
            int res=0;
            Node *cur=rt;
            while(true){
                assert(cur);
                if(val < cur->val){
                    if(cur->lch) cur=cur->lch;
                    else return res+1;
                }
                else{
                    res+=cur->lch?cur->lch->sz:0;
                    if(val==cur->val){
                        splay(cur);
                        return res+1;
                    }
                    else{
                        res+=cur->cnt;
                        if(cur->rch) cur=cur->rch;
                        else return res+1;
                    }
                }
            }
        }
        inline int query_kth_val(int k){
            Node *cur=rt;
            while(true){
                assert(cur);
                if(cur->lch && k<=cur->lch->sz) cur=cur->lch;
                else{
                    k-=cur->lch?cur->lch->sz:0;
                    if(k<=cur->cnt){
                        splay(cur);
                        return cur->val;
                    }
                    else{
                        k-=cur->cnt;
                        cur=cur->rch;
                    }
                }
            }
        }
        inline void del(int val){
            query_val_rk(val);//splay [val] to root
            if(rt->cnt>1){
                rt->cnt--;
                rt->pushup();
                return;
            }
            //now [val] is the root, we need to del the root and merge its left and right sons
            if((!rt->lch) && (!rt->rch)){
                delete rt;
                rt=nullptr;
            }
            else if(!rt->lch){
                Node *tmp=rt;
                rt=rt->rch;
                rt->fa=nullptr;
                delete tmp;
            }
            else if(!rt->rch){
                Node *tmp=rt;
                rt=rt->lch;
                rt->fa=nullptr;
                delete tmp;
            }
            else{
                Node *oldrt=rt,*ptr=getrtpre();
                oldrt->rch->fa=ptr;
                ptr->rch=oldrt->rch;
                delete oldrt;
                rt->pushup();
            }
        }
        inline int query_pre(int val){
            Node *ptr;
            int res;
            insert(val);
            ptr=getrtpre();
            res=ptr?ptr->val:-0x3f3f3f3f;
            del(val);
            return res;
        }
        inline int query_nxt(int val){
            Node *ptr;
            int res;
            insert(val);
            ptr=getrtnxt();
            res=ptr?ptr->val:-0x3f3f3f3f;
            del(val);
            return res;
        }
};

Treap

#define lch ch[0]
#define rch ch[1]
mt19937 mt_rand(time(NULL));
class Treap{
    private:
        struct Node{
            Node *ch[2];
            int val,pri,cnt,sz;
            Node(int v):val(v),cnt(1),sz(1){
                lch=rch=nullptr;
                pri=mt_rand();
            }
            void pushup(){
                sz=cnt;
                if(lch) sz+=ch[0]->sz;
                if(rch) sz+=ch[1]->sz;
            }
        };
        int qpre,qsuf;
        inline void rotate(Node *&cur,int dir){
            assert(cur);
            Node *tmp=cur->ch[!dir];
            cur->ch[!dir]=tmp->ch[dir];
            tmp->ch[dir]=cur;
            cur->pushup();
            tmp->pushup();
            cur=tmp;
        }
    public:
        Node *root=nullptr;
        void print(Node *x) {
            if (!x) return;
            cout<<x->val<<':'<<'[';
            print(x->lch);
            cout<<'|';
            print(x->rch);
            cout<<']';
        }
        void insert(Node *&cur,int val){
            if(cur==nullptr){
                cur=new Node(val);
                return;
            }
            else if(val==cur->val){
                cur->cnt++;
                cur->sz++;
            }
            else if(val<cur->val){
                insert(cur->lch,val);
                if(cur->lch->pri < cur->pri) rotate(cur,1);
                cur->pushup();
            }
            else{
                insert(cur->rch,val);
                if(cur->rch->pri < cur->pri) rotate(cur,0);
                cur->pushup();
            }
        }
        void del(Node *&cur,int val){
            assert(cur);
            if(val>cur->val){
                del(cur->rch,val);
                cur->pushup();
            }
            else if(val<cur->val){
                del(cur->lch,val);
                cur->pushup();
            }
            else{
                if(cur->cnt>1){
                    cur->cnt--;
                    cur->sz--;
                }
                else{
                    int state=(int)(cur->lch!=nullptr)+(int)(cur->rch!=nullptr)*2;
                    Node *tmp=cur;
                    switch(state){
                        case 0:{
                            delete cur;
                            cur=nullptr;
                            break;
                        }
                        case 1:{
                            cur=tmp->lch;
                            delete tmp;
                            break;
                        }
                        case 2:{
                            cur=tmp->rch;
                            delete tmp;
                            break;
                        }
                        case 3:{
                            if(cur->lch->pri < cur->rch->pri){
                                rotate(cur,1);
                                del(cur->rch,val);
                            }
                            else{
                                rotate(cur,0);
                                del(cur->lch,val);
                            }
                            cur->pushup();
                            break;
                        }
                    }
                }
            }
        }
        int query_rank(Node *cur,int val){
            assert(cur);
            int lftsz=cur->lch==nullptr ? 0 : cur->lch->sz;
            if(val==cur->val) return lftsz+1;
            else if(val<cur->val) return query_rank(cur->lch,val);
            else return lftsz+cur->cnt+query_rank(cur->rch,val);
        }
        int query_val(Node *cur,int rk){
            assert(cur);
            int lftsz=cur->lch==nullptr ? 0 : cur->lch->sz;
            if(rk<=lftsz) return query_val(cur->lch,rk);
            else if(rk<=lftsz+cur->cnt) return cur->val;
            else return query_val(cur->rch,rk-lftsz-cur->cnt);
        }
        int query_pre(Node *cur,int val){
            assert(cur);
            if(val<=cur->val){
                if(cur->lch) return query_pre(cur->lch,val);
            }
            else{
                qpre=cur->val;
                if(cur->rch) query_pre(cur->rch,val);
                return qpre;
            }
            return -0x3f3f3f3f;
        }
        int query_suf(Node *cur,int val){
            assert(cur);
            if(val>=cur->val){
                if(cur->rch) return query_suf(cur->rch,val);
            }
            else{
                qsuf=cur->val;
                if(cur->lch) query_suf(cur->lch,val);
                return qsuf;
            }
            return -0x3f3f3f3f;
        }
};

Fhq-Treap

#define lch t[pos].ls
#define rch t[pos].rs
mt19937 mt_rand(time(NULL));
class FhqTreap{
    private:
        int cnt;
        inline int newnode(int v){
            t[++cnt].sz=1;
            t[cnt].val=v;
            t[cnt].pri=mt_rand();
            t[cnt].ls=t[cnt].rs=0;
            return cnt;
        }
        inline void pushup(int pos){
            t[pos].sz=t[lch].sz+t[rch].sz+1;//tag
        }
        void split(int pos,int x,int &L,int &R){
            if(pos==0){
                L=R=0;
                return;
            }
            if(x>=t[pos].val){
                L=pos;
                split(rch,x,rch,R);
            }
            else{
                R=pos;
                split(lch,x,L,lch);
            }
            pushup(pos);
        }
        int merge(int L,int R){
            if(L==0||R==0) return L+R;
            if(t[L].pri<t[R].pri){
                t[L].rs=merge(t[L].rs,R);
                pushup(L);
                return L;
            }
            else{
                t[R].ls=merge(L,t[R].ls);
                pushup(R);
                return R;
            }
        }
    public:
        struct Node{
            int ls,rs,val,pri,sz;
        }t[MAXN];
        int root;
        inline void insert(int x){//tag
            int L,R;
            split(root,x,L,R);
            root=merge(merge(L,newnode(x)),R);
        }
        inline void del(int x){
            int L,R,P;
            split(root,x,L,R);
            split(L,x-1,L,P);
            root=merge(merge(L,merge(t[P].ls,t[P].rs)),R);
        }
        inline int query_rank(int x){
            int L,R,res;
            split(root,x-1,L,R);
            res=t[L].sz+1;
            merge(L,R);
            return res;
        }
        int query_kth(int pos,int k){
            if(k==t[lch].sz+1) return pos;
            else if(k<t[lch].sz+1) return query_kth(lch,k);
            else return query_kth(rch,k-t[lch].sz-1);//tag
        }
        inline int query_pre(int x){
            int L,R,res;
            split(root,x-1,L,R);
            res=t[query_kth(L,t[L].sz)].val;
            merge(L,R);
            return res;
        }
        inline int query_suf(int x){
            int L,R,res;
            split(root,x,L,R);
            res=t[query_kth(R,1)].val;
            merge(L,R);
            return res;
        }
};

标签：Node,cur,val,int,rch,模板,平衡,lch
From： https://www.cnblogs.com/SkyNet-PKN/p/17734117.html

相关文章

  • 使用ChatGPT快速构建优质网站模板的方法
    随着人工智能技术的不断发展，ChatGPT作为一种自然语言处理工具，正在被越来越多的领域所应用。其中，如何使用ChatGPT快速构建一个网站模板成为了许多开发者和企业关心的热点问题。本文将重点介绍如何使用ChatGPT快速构建一个网站模板，并突出其中的重点词汇或短语。确定网站目标和定位在......
  • Django 使用模板语法编写新闻中心（爬虫获取数据）
    1.创建项目#创建项目django-adminstartprojectnews#进入项目目录cdnews#创建apppythonmanage.pystartappapp012.修改app2.1添加html进入app01文件夹在app01文件夹中添加templates文件夹在templates文件夹中添加index.html<!DOCTYPEhtml><......
  • 模板语法
    在Django中，python是可以给html传值的1.python给模板传值defindex(request):returnrender(request,"index.html",{"名称1":"值1","名称2":"值2"})1.1render方法参数：defrender(request,template_name,context=None,conte......
  • 抽象类、抽象方法、模板方法设计模式的写法
    1、抽象方法：必须用abstarct修饰，只有方法签名，一定不能有方法体抽象类中不一定有抽象方法，有抽象方法的一定是抽象类  2、设计抽象类是为了更好的支持多态------------------------------------------------------------1、模板方法设计模式的写法（使用final修饰）a、定......
  • 使用js模板引擎心得
    最近几年随着web开发前后端分工越来越细，同时mvc、mvp模式大行其道，js模板引擎也越来越流行了js模板引擎很多，我经常用的是artTemplate、jsviews这两个模板引擎,12306用的就是jsviewsartTemplate特性:性能卓越，执行速度通常是Mustache与tmpl的20多倍（性能测试）支持运行时调试，可......
  • 函数模板_构造函数栈溢出
    前言最近写一个任务队列，可以支持存入返回值为void的任意函数对象。需要定义一个Task模板，来存储函数对象以及参数。大致的实现如下：classTask{public:template<typenameFunc,typename...Args>Task(Func&&f,Args&&...args):func_(std::bind(std::for......
  • idea java代码注释模板制作 idea类注释模板设置【转载】
    一、类模板设置1、进入设置页面：File-->settings-->Editor-->FileandCodeTemplates-->Files2、设置类、接口、枚举模板信息3、点击Apply应用设置二、方法模板设置1、同样打开设置：File-->settings-->Editor-->LiveTemplates2、新建模板组：命名为userDefine3、选中新建的模板组，新......
  • P3812 【模板】线性基
    题意给定\(n\)个整数，求这\(n\)个整数的异或最大值。Sol线性基模板题。考虑维护一个线性基。插入一个数时，从高位往低位枚举。遇到第一个基中不存在的位，就将该数加入基，否则异或下去。询问最大值，考虑贪心，若当前\(ans^p[i]>ans\)则直接\(ans^=p[i]\)。#include<i......
  • java项目开发常用配置文件模板
    mybatisconfig文件1<?xmlversion="1.0"encoding="UTF-8"?>2<!DOCTYPEconfiguration3PUBLIC"-//mybatis.org//DTDConfig3.0//EN"4"http://mybatis.org/dtd/mybatis-3-config.dtd">5......
  • chart模板实战
    参考：https://helm.sh/zh/docs/chart_template_guide/getting_started/https://helm.sh/zh/docs/chart_template_guide/function_list/一.入门chart1.创建一个charthelmcreatemychart查看目录结构[root@k8s-masterhelm-test]#treemychart/mychart/├──charts├......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99