非旋转Treap 学习笔记

发表于 | 分类于 | | + s

模板及讲解
非旋转Treap：
Treap=Tree+heap，即键值$key$(满足排序二叉树性质(左小右大)，并且按照中序遍历有序)，附加值$val$(满足堆性质(孩子都比父节点小))
核心操作$O(nlogn)$：

  • $newNode(x)$ 新建一个以$x$为权值的点
  • $merge(a, b)$ 把$a$树和$b$树合并，必须满足$\forall key_a < \forall key_b$
  • $split_v(a,v,x,y)$把$a$树按权值$v$分成$x,y$两棵树，一棵树小于等于$v$，一棵树大于$v$
  • $split_k(a,v,x,y)$把$a$树按前$k$个分配成$x,y$两棵树

能够实现的操作$O(nlogn)$：

  • $rank(x)$ 查询$x$的排名
  • $kth(x)$ 查询第$x$大的数
  • $pre(x)$ 查询$x$的前驱
  • $succ(x)$ 查询$x$的后继
  • $insert(x)$ 插入一个数权值为$x$
  • $del(x)$ 删除一个权值为$x$的数

具体可以看相关代码
写时注意：
1 不要忘了srand(19260817)
2 $split$里$x, y$用*&
3 主程序记得加$initTreap()$
4 $merge$前面记得加赋值

可持久化Treap：
暂略

常见题型
1、直接使用操作完成
Q: 求第$k$大\求$x$的排名……
解: 直接套模板。
例题: bzoj3224
2、操作区间
Q: 翻转某个区间
解: 非旋Treap处理区间。
例题: bzoj3223

相关代码
bzoj3224非旋转Treap模板：包括基本操作

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
struct Treap *null, *pit, *root;//自建的null节点，内存池指针 
struct Treap {
    int key, val, s;//键值(满足排序二叉树性质)，附加值(满足堆性质)，以本节点为根的子树大小
    Treap *lc, *rc;//Treap 左右结点 
    Treap() {};
    void init(int key) {this->key = key, val = rand(), lc = rc = null, s = 1;}//初始化 
    void maintain() {s = lc->s + rc->s + 1;}//更新，维护以本节点为根的子树大小
}pool[MAXN];//内存池 
Treap* newNode(int key) {
    pit->init(key);
    return pit++;
}
Treap* merge(Treap *a, Treap *b) {//合并两棵Treap，所有key(a)<key(b)才能合并，为了满足排序二叉树性质
    if (a == null) return b;
    if (b == null) return a;
    if (a->val < b->val) {
        a->rc = merge(a->rc, b), a->maintain();
        //a小自然a要在b的上面，满足堆性质
        return a;
    }
    if (a->val >= b->val) {
        b->lc = merge(a, b->lc), b->maintain();
        //a大自然a要在b的下面，满足堆性质
        return b;
    }
}
void split_v(Treap *o, int v, Treap *&x, Treap *&y) {//用权值分开一棵Treap，分开的第一棵根为x，第二棵根为y。x，y可以称为左右子树“下一个”位置，也就是如果还有满足左边的，就放在x或者y的位置
    if (o == null) x = y = null; else {
        if (o->key <= v) {
            x = o, split_v(o->rc, v, o->rc, y);//x = o说明o左边全部放进x，递归右子树
        } else y = o, split_v(o->lc, v, x, o->lc);
        o->maintain();
    }
}
void split_k(Treap *o, int k, Treap *&x, Treap *&y) {//按前k个分配分开一棵Treap，分开的第一棵根为x，第二棵根为y。x，y可以称为左右子树“下一个”位置，也就是如果还有满足左边的，就放在x或者y的位置
    if (o == null) x = y = null; else {
        if (k <= o->lc->s) {
            y = o, split_k(o->lc, k, x, o->lc);//y = o说明o右边全部放进y，递归左子树
        } else x = o, split_k(o->rc, k - o->lc->s - 1, o->rc, y);
        o->maintain();
    }
}
void insert(int v) {//插入一个数 
    Treap *a, *b;
    split_v(root, v, a, b);
    root = merge(merge(a, newNode(v)), b);
}
void del(int v) {//删除一个数 
    Treap *a, *b;
    split_v(root, v, a, b);
    Treap *c, *d;
    split_v(a, v - 1, c, d);
    d = merge(d->lc, d->rc);
    a = merge(c, d), root = merge(a, b);
}
int kth(int k) {//查询排名为k的数
    Treap *a, *b;
    split_k(root, k - 1, a, b);
    Treap *c, *d;
    split_k(b, 1, c, d);
    int ret = c->key;
    b = merge(c, d), root = merge(a, b);
    return ret;
}
int rk(int x) {//查询x的排名
    Treap *a, *b;
    split_v(root, x - 1, a, b);
    int ret = a->s + 1;
    root = merge(a, b);
    return ret;
}
int pre(int x) {//求x的前驱 
    Treap *a, *b;
    split_v(root, x - 1, a, b);
    Treap *c, *d;
    split_k(a, a->s - 1, c, d);
    int ret = d->key;
    a = merge(c, d), root = merge(a, b); 
    return ret;
}
int succ(int x) {//求x的后继 
    Treap *a, *b;
    split_v(root, x, a, b);
    Treap *c, *d;
    split_k(b, 1, c, d);
    int ret = c->key;
    b = merge(c, d), root = merge(a, b); 
    return ret;
}
void initTreap() {
     srand(19260827);//置随机数种子 
     pit = pool;//指针指向内存池 
     null = newNode(0), null->s = 0;//初始化自建的null节点
     root = null;//初始化树根 
}
void clean() {}
void solve() {
    clean();
    initTreap();
    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int opt, x;
        scanf("%d%d", &opt, &x);
        switch (opt) {
            case 1: insert(x); break;
            case 2: del(x); break;
            case 3: printf("%d\n", rk(x)); break;
            case 4: printf("%d\n", kth(x)); break;
            case 5: printf("%d\n", pre(x)); break;
            case 6: printf("%d\n", succ(x)); break;
        }
    }
}
int main() {
    solve();
    return 0;
}
------ 本文结束 ------