2020-07-01 17:10 已编辑山东大学 Java

关注

fhq_treap 小结

简介

$fhq\_treap$ 是一种非旋平衡树。在学习这篇文章之前，还是先学习一下普通 $treap$ 吧

优点

相比于普通的 $treap$ ，它可以处理区间操作。
相比于 $splay$ ，它简洁易懂，代码也较短。

缺点

要比 $splay$ 和 $treap$ 慢

基础操作

$fhq\_treap$ 最基本的两个操作就是分裂和合并。

分裂

即把一个 $treap$ 分为两个。有按照权值分和按照大小分两种方式。
具体方法:
比着代码划拉划拉就知道了(懒)。
按权值分

void split(int rt,int val,int &x,int &y) {
    if(!rt) {
        x = y = 0;
        return;
    }
    if(TR[rt].w <= val) {
        x = rt;split(rs,val,rs,y);
    }
    else {
        y = rt;split(ls,val,x,ls);
    }
    update(rt);
}

按大小分

void split(int rt,int K,int &x,int &y) {
    if(!rt) {
        x = y = 0;return;
    }
    down(rt);
    if(K <= TR[ls].siz) {
        y = rt;split(ls,K,x,ls);
    }
    else {
        x = rt;split(rs,K - TR[ls].siz - 1,rs,y);
    }
    update(rt);
}

合并

即把两个 $treap$ 合并为一个。
注意要让id形成一个堆，且合并的两个树满足其中一个中的权值全部小于另一个。
具体方法:
比较简单，参考代码吧。。

int merge(int x,int y) {
    if(!x || !y) return x + y;
    if(TR[x].id < TR[y].id) {
        TR[x].son[1] = merge(TR[x].son[1],y);
        update(x);
        return x;
    }
    TR[y].son[0] = merge(x,TR[y].son[0]);
    update(y);
    return y;
}

其他操作

插入

插入一个权值为 $x$ 的数。
只需要将原来的 $treap$ 按权值 $x$ 分为 $L,R$ 两棵树。
然后把 $x$ 节点当成一个 $treap$ 与 $L$ 合并起来。然后再整体和 $R$ 合并起来。

void insert(int x) {
    int L,R;
    split(root,x,L,R);
    root = merge(merge(L,new_node(x)),R);
}

删除

删除一个权值为 $x$ 的数。
将原来的 $treap$ 按权值 $x$ 分为 $L,R$ 两棵子树。再按权值 $x-1$ 将 $L$ 分为 $L,rt$ 两棵子树。
这时 $rt$ 中就全都是权值为x的点了。删除根节点(也就是将根的两个孩子合并起来)。
操作完成别忘了合并回去。

void del(int x) {
    int L,R,rt;
    split(root,x,L,R);
    split(L,x - 1,L,rt);
    rt = merge(ls,rs);
    root = merge(merge(L,rt),R);
}

查询排名

查询权值 $x$ 的排名(定义为比 $x$ 小的数的数量+1)。
将原 $treap$ 按权值 $x-1$ 分为 $L,R$ 两棵子树。 $L$ 的大小+1就是答案了。
操作完成别忘了合并回去。

int Rank(int x) {
    int L,R;
    split(root,x - 1,L,R);
    int ret = TR[L].siz + 1;
    root = merge(L,R);
    return ret;
}

查询第k大

查询排名为 $k$ 的数字。
如果排名小于等于左子树大小就查询左子树。
如果排名大于左子树大小+1就查询右子树，并且 $k-=$ 左子树大小
否则返回当前节点。

int kth(int rt,int x) {
    while(1) {
        if(x == TR[ls].siz + 1) return rt; 
        if(x <= TR[ls].siz) rt = ls;
        else {
            x -= TR[ls].siz + 1;
            rt = rs;
        }
    }
}

前驱

查询比 $x$ 小的数中最大的数。
按权值 $x-1$ 将原 $treap$ 分为 $L,R$ 两棵子树。 $L$ 子树中最大的那个就是答案。
操作完成别忘了合并回去。

int pre(int x) {
    int L,R;
    split(root,x - 1,L,R);
    int ret = kth(L,TR[L].siz);
    root = merge(L,R);return ret;
}

后继

查询比 $x$ 大的数中最小的数。
按权值 $x$ 将原 $treap$ 分为 $L,R$ 两棵子树。 $R$ 子树中最小的就是答案。
操作完成别忘了合并回去。

int nxt(int x) {
    int L,R;
    split(root,x,L,R);
    int ret = kth(R,1);
    root = merge(L,R);return ret;
}

处理区间

对区间 $l,r$ 进行处理。
先按大小 $r$ 将原 $treap$ 分为 $L,R$ 两棵子树。
再按大小 $l-1$ 将 $L$ 分为 $L1,L2$ 两棵子树。 $L2$ 子树就是要处理的区间了。
操作完成别忘了合并回去。

void reverse(int l,int r) {
    int L,R,rt,tmp;
    split(root,r + 1,L,R);
    split(L,l,tmp,rt);
    TR[rt].rev ^= 1;
    root = marge(marge(tmp,rt),R);
}

例题

bzoj3224

/*
* @Author: wxyww
* @Date:   2019-04-13 08:47:22
* @Last Modified time: 2019-04-13 11:24:25
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
#define ls TR[rt].son[0]
#define rs TR[rt].son[1]
const int N = 100000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<&#39;0&#39;||c>&#39;9&#39;) {
        if(c==&#39;-&#39;) f=-1;
        c=getchar();
    }
    while(c>=&#39;0&#39;&&c<=&#39;9&#39;) {
        x=x*10+c-&#39;0&#39;;
        c=getchar();
    }
    return x*f;
}
struct node {
    int w,id,siz,son[2];
}TR[N];
int root,tot;
int new_node(int val) {
    ++tot;
    TR[tot].w = val,TR[tot].id = rand(),TR[tot].siz = 1;
    return tot;
}
void update(int rt) {
    TR[rt].siz = TR[ls].siz + TR[rs].siz + 1;
}
int merge(int x,int y) {
    if(!x || !y) return x + y;
    if(TR[x].id < TR[y].id) {
        TR[x].son[1] = merge(TR[x].son[1],y);
        update(x);
        return x;
    }
    TR[y].son[0] = merge(x,TR[y].son[0]);
    update(y);
    return y;
}
void split(int rt,int val,int &x,int &y) {
    if(!rt) {
        x = y = 0;
        return;
    }
    if(TR[rt].w <= val) {
        x = rt;split(rs,val,rs,y);
    }
    else {
        y = rt;split(ls,val,x,ls);
    }
    update(rt);
}
void insert(int x) {
    int L,R;
    split(root,x,L,R);
    root = merge(merge(L,new_node(x)),R);
}
void del(int x) {
    int L,R,rt;
    split(root,x,L,R);
    split(L,x - 1,L,rt);
    rt = merge(ls,rs);
    root = merge(merge(L,rt),R);
}
int Rank(int x) {
    int L,R;
    split(root,x - 1,L,R);
    int ret = TR[L].siz + 1;
    root = merge(L,R);
    return ret;
}
int kth(int rt,int x) {
    while(1) {
        if(x == TR[ls].siz + 1) return rt; 
        if(x <= TR[ls].siz) rt = ls;
        else {
            x -= TR[ls].siz + 1;
            rt = rs;
        }
    }
}
int pre(int x) {
    int L,R;
    split(root,x - 1,L,R);
    int ret = kth(L,TR[L].siz);
    root = merge(L,R);return ret;
}
int nxt(int x) {
    int L,R;
    split(root,x,L,R);
    int ret = kth(R,1);
    root = merge(L,R);return ret;
}
int main() {
    srand(time(0));
    int n = read();
    while(n--) {
        int opt = read(),x = read();
        if(opt == 1) insert(x);
        else if(opt == 2) del(x);
        else if(opt == 3) printf("%d\n",Rank(x));
        else if(opt == 4) printf("%d\n",TR[kth(root,x)].w);
        else if(opt == 5) printf("%d\n",TR[pre(x)].w);
        else printf("%d\n",TR[nxt(x)].w);
    }
    return 0;
}

bzoj3223

/*
* @Author: wxyww
* @Date:   2019-04-13 10:46:59
* @Last Modified time: 2019-04-13 11:24:56
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
#define ls TR[rt].son[0]
#define rs TR[rt].son[1]
const int N = 100000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<&#39;0&#39;||c>&#39;9&#39;) {
        if(c==&#39;-&#39;) f=-1;
        c=getchar();
    }
    while(c>=&#39;0&#39;&&c<=&#39;9&#39;) {
        x=x*10+c-&#39;0&#39;;
        c=getchar();
    }
    return x*f;
}
struct node {
    int w,id,siz,rev,son[2];
}TR[N];
int tot;
int root,n,m;
void update(int rt) {
    TR[rt].siz = TR[ls].siz + TR[rs].siz + 1;
}
void down(int rt) {
    if(TR[rt].rev) {
        TR[ls].rev ^= 1;
        TR[rs].rev ^= 1;
        swap(ls,rs);
        TR[rt].rev ^= 1;
    }
}
int new_node(int x) {
    ++tot;
    TR[tot].id = rand();TR[tot].siz = 1;TR[tot].w = x;TR[tot].rev = 0;
    return tot;
}
int marge(int x,int y) {
    if(!x || !y) return x + y;
    down(x),down(y);
    if(TR[x].id < TR[y].id) {
        TR[x].son[1] = marge(TR[x].son[1],y);
        update(x);
        return x;
    }
    else {
        TR[y].son[0] = marge(x,TR[y].son[0]);
        update(y);
        return y;
    }
}

void split(int rt,int K,int &x,int &y) {
    if(!rt) {
        x = y = 0;return;
    }
    down(rt);
    if(K <= TR[ls].siz) {
        y = rt;split(ls,K,x,ls);
    }
    else {
        x = rt;split(rs,K - TR[ls].siz - 1,rs,y);
    }
    update(rt);
}
void reverse(int l,int r) {
    int L,R,rt,tmp;
    split(root,r + 1,L,R);
    split(L,l,tmp,rt);
    TR[rt].rev ^= 1;
    root = marge(marge(tmp,rt),R);
}
int build(int l,int r) {
    if(l > r) return 0;
    int mid = (l + r) >> 1;
    int rt = new_node(mid - 1);
    ls = build(l,mid - 1);
    rs = build(mid + 1,r);
    update(rt);
    return rt;
}
void print(int rt) {
    if(!rt) return;
    down(rt);
    print(ls);
    if(TR[rt].w >= 1 && TR[rt].w <= n) printf("%d ",TR[rt].w);
    print(rs);
}
int main() {
    n = read(),m = read();
    root = build(1,n + 2);
    while(m--) {
        int l = read(),r = read();
        reverse(l,r);
    }
    print(root);
    return 0;
}