Cauphenuny's blog

无旋Treap

发表于 更新于 分类于 ， ，

参考：blog1 | blog2

定义一下变量：

1
2
3
4
5
6
7
8
9
struct Node {
    int ls;//每个点的左儿子
    int rs;//每个点的右儿子
    int val;//每个点的权值
    int rnd;//每个点的随机权值
    int siz;//以每个点为根的树的大小
} tree[MAXN];
int root;//根节点编号
int tot;//节点总数

主要有两个核心操作：split(int rt, int &a, int &b, int k) 和 merge(int a, int b, int &rt) ，分别表示将一颗 treap(rt)\mathsf{treap(rt)} 按权值分裂成两颗 treap(a)\mathsf{treap(a)} 和 treap(b)\mathsf{treap(b)} 以及将两颗 treap\mathsf{treap} 合并。

基本操作

分裂

split(int rt, int &a, int &b, int val)

递归处理，设当前节点为 rtrt，要按值 valval 分裂成两颗树 aa 和 bb。

若 rt<=valrt <= val ，则 rtrt 以及它的左子树都可以并入 aa 节点，下一步要将 rt.rsrt.rs 分裂，如下图。

若 rt>valrt > val ，则 rtrt 以及它的右子树都可以并入 bb 节点，下一步要将 rt.lsrt.ls 分裂，如下图。

如果 rt=0rt=0 即达到了递归边界，这时候要怎么办呢？

赋值 a = b = 0; 表示当前 aa， bb 均为空节点，即上图的绿色和蓝色节点都为空。因为调用函数时是引用的变量，因此 aa， bb 的改变也会影响到上级的节点的左儿子或者右儿子。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void split_by_val(int rt, int &a, int &b, int val) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (p[rt].val <= val) {
        a = rt;
        split_by_val(p[rt].rs, p[a].rs, b, val);
    } else {
        b = rt;
        split_by_val(p[rt].ls, a, p[b].ls, val);
    }
    pushup(rt);
}

排名分裂是类似的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void split_by_rank(int rt, int &a, int &b, int rank) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    int ls = p[rt].ls, rs = p[rt].rs;
    if (p[ls].siz + 1 <= rank) {
        a = rt;
        split_by_rank(rs, p[a].rs, b, rank - p[ls].siz - 1);
    } else {
        b = rt;
        split_by_rank(ls, a, p[b].ls, rank);
    }
    pushup(rt);
}

合并

操作：merge(a, b, rt)：将 aa，bb 合并至 rtrt ，（∀x∈treap(a),y∈treap(b)\forall x\in treap(a),y\in treap(b) 有 val(x)<val(y)val(x)<val(y)）。

由于要满足堆性质，所以要分情况考虑。

若 rnd(a)≤rnd(b)rnd(a) \le rnd(b) 则将 aa 和它的左子树复制到 rtrt 上，赋值 rt = a ，继续递归 merge(a.rs, b, rt.rs)。

反之，则将 bb 和它的右子树复制到 rtrt 上，赋值 rt = b ，继续递归 merge(a, b.ls, rt.ls)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge(int a, int b, int &rt) {
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (p[a].rnd <= p[b].rnd) {
        rt = a;
        merge(p[a].rs, b, p[rt].rs);
        pushup(a);
    } else {
        rt = b;
        merge(a, p[b].ls, p[rt].ls);
        pushup(b);
    }
    pushup(rt);
}

其他操作

插入 insert(a)

将树按权值 aa 分裂成两颗树 xx 和 yy，然后新建一个节点 zz 合并 xx 与 zz 至 uu，合并 uu 和 yy 至 rootroot

代码

1
2
3
4
5
6
7
void insert(int &rt, int val) {
    int x, y, z, u;
    split_by_val(rt, x, y, val);
    z = newnode(val);
    merge(x, z, u);
    merge(u, y, rt);
}

删除一个权值为 vv 的节点 del(v)

将树 rootroot 按权值 vv 分裂为 aa 和 bb 。

再将 aa 按权值 v−1v - 1 分裂成 xx 和 yy。

接着，merge(y.ls, y.rs, y) ，表示去掉一个 yy 树中的节点，形成的新的树的根节点仍然是 yy ，再 merge(x, y, a)，merge(a, b, root)，重新把几颗树合并到根节点。

代码

1
2
3
4
5
6
7
8
void del(int &rt, int val) {
    int x, y, a, b;
    split_by_val(rt, a, b, val);
    split_by_val(a, x, y, val - 1);
    merge(p[y].ls, p[y].rs, y);
    merge(x, y, a);
    merge(a, b, rt);
}

删除所有权值为 vv 的节点 multidel(v)

与上面类似，最后一步直接 merge(x, b, root) 。

代码

1
2
3
4
5
6
void multidel(int &rt, int val) {
    int x, y, a, b;
    split_by_val(rt, a, b, val);
    split_by_val(a, x, y, val - 1);
    merge(x, b, rt);
}

排名 getrank(rt, v)

直接按照 v−1v-1 的权值把树 rtrt 分开为 xx 和 yy，那么 xx 树中最大的应该小于等于 a−1a-1 ，那么 aa 的排名就是size[x]+1size[x]+1。

代码：

1
2
3
4
5
6
7
8
9
int getrank(int &rt, int val) {
    int x, y, res;
    split_by_val(rt, x, y, val - 1);
    //puts("x:");printtree(x);puts("");
    //puts("y:");printtree(y);puts("");
    res = p[x].siz + 1;
    merge(x, y, rt);
    return res;
}

查询 kk 小值 getval(rt, k)

记当前节点的左子树大小为 sizsiz 。
siz=k−1siz=k-1，那么 tree[rt].valtree[rt].val 就是答案。
siz>k−1siz>k-1，递归查找左子树的 kk 小值
siz<k−1siz<k-1，递归查找右子树的 k−siz−1k-siz-1小值

代码

1
2
3
4
5
6
7
8
9
int getval(int rt, int k) {
    if (p[p[rt].ls].siz < k - 1) {
        return getval(p[rt].rs, k - p[p[rt].ls].siz - 1);
    } else if (p[p[rt].ls].siz > k - 1) {
        return getval(p[rt].ls, k);
    } else {
        return p[rt].val;
    }
}

前驱 getprev(v)

因为要小于 vv ，所以我们还是按照 v−1v-1 的权值划分 xx ，现在 xx 中最大的数一定小于等于 a−1a-1，所以我们直接输出xx 中最大的数就好

代码

1
2
3
4
5
6
7
8
9
int getprev(int &rt, int val) {
    int x, y, res;
    split_by_val(rt, x, y, val - 1);
    //printtree(x);puts("");
    //printtree(y);puts("");
    res = getval(x, p[x].siz);
    merge(x, y, rt);
    return res;
}

后继 getnext(v)

按照 vv 的权值划分 xx 和 yy，现在 yy 中最小的数一定大于 aa 输出 yy 中最小的数。

代码

1
2
3
4
5
6
7
int getnext(int &rt, int val) {
    int x, y, res;
    split_by_val(rt, x, y, val);
    res = getval(y, 1);
    merge(x, y, rt);
    return res;
}

扩展内容

持久化：link

水掉splay：link

几道习题：
P1486 (NOI2004)郁闷的出纳员
P2596 (ZJOI2006)书架 总结