FHG无旋treap

标签：sz val merge int 无旋 FHG tr treap now

FHG无旋treap能做大部分splay能完成的操作，而且代码比较短，思路比较splay来说也更加易懂一些，是性价比很高的数据结构，推荐入手，视频可以看b站Agoh大佬的视频，讲的很清晰，但是splay也是要学的，不是说学了FHGtreap就可以完全替代splay，splay的灵活度还是高于FHGtreap的。

前置知识：平衡树，动态开点

下面我们来学学FHG无旋treap的思路和具体如何实现！！

 

主要有两个函数实现，spilt(), merge()

首先是一棵树要维护的信息

struct Node{
    int l, r, val;
    int key; 
    // 还有具体题目中需要维护的信息
}
int root, idx;

动态开点函数

int Newnode(int val)
{//开点并初始化
    int u = ++ idx;
    tr[u].key = rand();// key用来维护大根堆(小根堆)的性质，随机值可以保证树的高度平均值是logn
    tr[u].val = val;
    return u;
}

按值分裂

//按值分裂，小于等于val的为x树，大于等于val的为y树
void spilt(int now, int val, int &x, int &y)
{
    if(!now) x = y = 0; 
    else
    {
        if(tr[u].val <= val)//如果根节点权值小于val，根节点和左子树分裂到x树，然后递归到右子树继续分裂
        {
            x = now;
            spilt(tr[now].r, val, tr[x].r, y);
        }
        else
        {//同上
            y = now;
            spilt(tr[now].l, val, x, tr[y].l);
        }
        pushup(now);//维护一下树的信息
    }
}

按树的大小分裂

//按树的大小分裂，分裂以后x树的大小为sz，其余为y树
void spilt(int now, int sz, int &x, int &y)
{
    if(!now) x = y = 0;
    else
    {
        if(tr[tr[u].l] < sz)
        {
            x = now;
            spilt(tr[now].r, sz - tr[tr[u].l].sz - 1, tr[x].r, y);
        }
        else 
        {
            y = now;
            spilt(tr[now].l, sz, x, tr[y].l);
        }
        pushup(now);
    }
}

merge（合并）

int merge(int x, int y)//将x，y树合并，返回根节点
{
    if(!x || !y) return x + y;
    else
    {
        if(tr[x].key >= tr[y].key) 
        // 维护大根堆的性质，如果x的key大于y的key，合并之后x为根节点，y是x的右儿子
        {
            tr[x].r = merge(tr[x].r, y);
            pushup(x);
            return x;
        }
        else
        {//同上
            tr[y].l = merge(x, tr[y].l);
            pushup(y);
            return y;
        }
    }
}

 

模板题：https://www.luogu.com.cn/problem/P3369

 

代码展示：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;


#define x first
#define y second


typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<PII, int> PIII;
typedef pair<LL, LL> PLL;
const int N = 100010, M = 50000, mod = 998244353, INF = 0x3f3f3f3f;


struct tree{
    int l, r;
    int key, val;
    int sz;
}tr[N];
int root, cnt;


int newNode(int val)
{
    tr[++ cnt].key = rand();
    tr[cnt].val = val;
    tr[cnt].sz = 1;
    return cnt;
}

void update(int now)
{
    tr[now].sz = tr[tr[now].l].sz + tr[tr[now].r].sz + 1;
}

void spilt(int now, int val, int &x, int &y)
{
    if(!now) x = y = 0;
    
    else
    {
        if(tr[now].val <= val)
        {
            x = now;
            spilt(tr[now].r, val, tr[now].r, y);
        }
        else 
        {
            y = now;
            spilt(tr[now].l, val, x, tr[now].l);
        }
        update(now);
    }
}

int merge(int x, int y)
{
    if(!x || !y) return x + y;
    if(tr[x].key > tr[y].key)
    {
        tr[x].r = merge(tr[x].r, y);
        update(x);
        return x;
    }
    else
    {
        tr[y].l = merge(x, tr[y].l );
        update(y);
        return y;
    }
}

int x, y, z;
void insert(int val)
{
    spilt(root, val, x, y);
    root = merge(merge(x, newNode(val)), y);
}

void remove(int val)
{
    spilt(root, val, x, z);
    spilt(x, val - 1, x, y);
    y = merge(tr[y].l, tr[y].r);
    root = merge(merge(x, y), z);
}

void get_rank(int val)
{
    spilt(root, val - 1, x, y);
    printf("%d\n", tr[x].sz + 1);
    root = merge(x, y);
}

void get_num(int rank)
{
    int now = root;
    while(now)
    {
        if(tr[tr[now].l].sz + 1 == rank) break;
        else if(tr[tr[now].l].sz >= rank) now = tr[now].l;
        else
        {
            rank -= tr[tr[now].l].sz + 1;
            now = tr[now].r;
        }
    }
    printf("%d\n", tr[now].val);
}

void get_pre(int val)
{
    spilt(root, val - 1, x, y);
    int now = x;
    while(tr[now].r) now = tr[now].r;
    printf("%d\n", tr[now].val);
    root = merge(x, y);
}

void get_next(int val)
{
    spilt(root, val, x, y);
    int now = y;
    while(tr[now].l) now = tr[now].l;
    printf("%d\n", tr[now].val);
    root = merge(x, y);
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ )
    {
        int op, x;
        scanf("%d %d", &op, &x);
        if(op == 1) insert(x);
        else if(op == 2) remove(x);
        else if(op == 3) get_rank(x);
        else if(op == 4) get_num(x);
        else if(op == 5) get_pre(x);
        else get_next(x);
    }
    return 0;
}

 

标签：sz,val,merge,int,无旋,FHG,tr,treap,now
From： https://www.cnblogs.com/jay1573/p/16622848.html