FHQ-Treap

发表于 更新于 分类于 阅读次数： Valine： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

期末考试前写这玩意，我危。

FHQ-Treap

为啥不旋转了？

转来转去不可爱！难写难调（较非旋 Treap 而言），结构还不稳定，不能可持久化！

怎么分裂/合并？

FHQ-Treap 维护值域大概是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
//split 函数的作用是将一棵 FHQ-Treap 分裂成权值 <=val 和 >val 的两部分
void split(int &now,int x,int y,int val) {
    if(!now) {x=y=0;return ;}
    pushdown(now); //别忘记 pushdown!
    if(t[now].val<=val) {
        x=now;
        split(t[now].r,t[x].r,y,val);
    } else {
        y=now;
        split(t[now].l,x,t[y].l,val);
    }
    pushup(now);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//merge 函数的作用是将两棵左边权值严格比右边小的 FHQ-Treap 按堆权合并成一棵树
int merge(int x,int y) {
    if(!x||!y) return x+y;
    if(t[x].rnk<t[y].rnk) {
        pushdown(x);
        t[x].r=merge(t[x].r,y);
        pushup(x);
        return x;
    } else {
        pushdown(y);
        t[y].l=merge(x,t[y].l);
        pushup(y);
        return y;
    }
}

除此之外，FHQ-Treap 还可以用来维护序列。

具体来说，我们不再按照 val 分裂，而是选择按照 size 分裂。这样可以满足其映射的序列的下标满足二叉搜索树性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
//split 函数的作用是将一棵 FHQ-Treap 分裂成下标 <=k 与 >k 的两部分
void split(int &now,int x,int y,int k) {
    if(!now) {x=y=0;return ;}
    pushdown(now); //别忘记 pushdown!
    if(t[t[now].l].sz<k) {
        x=now;
        split(t[now].r,t[x].r,y,k-t[t[now].l].sz-1);
    } else {
        y=now;
        split(t[now].l,x,t[y].l,k);
    }
    pushup(now);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//merge 函数的作用是将两棵左边下标严格比右边小的 FHQ-Treap 按堆权合并成一棵树
int merge(int x,int y) {
    if(!x||!y) return x+y;
    if(t[x].rnk<t[y].rnk) {
        pushdown(x);
        t[x].r=merge(t[x].r,y);
        pushup(x);
        return x;
    } else {
        pushdown(y);
        t[y].l=merge(x,t[y].l);
        pushup(y);
        return y;
    }
}

其他操作？

可以轮番调用 split 和 merge 来解决。

维护序列可以打标记。