非旋转 Treap 及可持久化 Treap

Published on 2016-03-26

基本知识：普通堆，二叉搜索树，可持久化基本思想。

介绍

性质

Treap = Tree + Heap
Treap 是一颗同时拥有二叉搜索树和堆性质的一颗二叉树
Treap 有两个关键字，在这里定义为：

$\text{key}$ ：满足二叉搜索树性质，即中序遍历按照 $\text{key}$ 值有序。
$\text{val}$ ：满足堆性质，即对于任何一颗以 $x$ 为根的子树， $x$ 的 $\text{val}$ 值为该子树的最值，方便后文叙述，定义为最小值。为了满足期望， $\text{val}$ 值是一个随机的权值，用来保证树高期望为 $\log n$ 。剩下的 $\text{key}$ 值则是用来维护我们想要维护的一个权值，此为一个二叉搜索树的基本要素。

给出结构体定义：

struct Treap {
    int key, val;
    Treap *ch[2];
};

功能

支持操作：

基本操作：
Build 「构造Treap」 $O(n)$
Merge「合并」 $O(\log n)$
Split「拆分」 $O(\log n)$
Newnode「新建节点」 $O(1)$
可支持操作：
Insert「Newnode+Merge」 $O(\log n)$
Delete「Split+Split+Merge」 $O(\log n)$
Find_kth「Split+Split」 $O(\log n)$
Query「Split+Split」 $O(\log n)$

实现

建树

建树之前，按照惯例，先看看一个叫笛卡尔树的东西。

笛卡尔树

笛卡尔树是一棵二叉树，树的每个节点有两个值，一个为 $\text{key}$ ，一个为 $\text{val}$ 。光看 $\text{key}$ 的话，笛卡尔树是一棵二叉搜索树，每个节点的左子树的 $\text{key}$ 都比它小，右子树都比它大；光看 $\text{val}$ 的话，笛卡尔树有点类似堆，根节点的 $\text{val}$ 是最小（或者最大）的，每个节点的 $\text{val}$ 都比它的子树要大。
笛卡尔树构造是和 Treap 完全一样的，如果 $\text{key}$ 值是有序的，那么笛卡尔树的构造是线性的，所以我们只要把 Treap 当作一颗笛卡尔树构造就可以了。

笛卡尔树的构造

这里对于 $\text{val}$ 而言，我们构造小根堆。
我们将一个节点表示为： $(\text{key}, \text{val})$ 。首先将所有节点按照 $\text{key}$ 从小到大排序。
引入一个栈，栈底存放一个元素 $(-\infty, -\infty)$ ，表示超级根，这样保证它总在最上面，他的右儿子即为我们真正的树根。这个栈，维护了笛卡尔树最右边的一条链上面的元素。
从前往后遍历 $(\text{key}, \text{val})$ ：

对于每一个 $(\text{key}_i, \text{val}_i)$ ，从栈中找出（从栈顶往栈底遍历）第一个小于等于 $\text{val}_i$ 的元素 $\text{val}_j$
将 $\text{val}_j$ 之上即 $\text{val} > \text{val}_i$ 的点全部弹出。
在树中，将 $j$ 的右子树挂在 $i$ 的左子树上，将 $i$ 挂在原来 $j$ 的右子树的位置。

用很不严谨的话说，就是一个节点 $i$ 来了，我们只考虑在最右边的链插入这个节点。由于要维护堆性质，如果它的 $\text{val}$ 比之前的都大，那么他就可以挂在最右边的链的最后一个，由于 $\text{key}$ 从小到大，不违反二叉搜索树的性质。如果它比之前的某些小，那么找到小于等于它 $\text{val}$ 的元素 $j$ ，变成它的右儿子，那么堆的性质满足了，又要满足二叉搜索树的性质，所以把原先 $j$ 的右儿子挂在 $i$ 的左子树。

POJ: 1785 可以练一练构造笛卡尔树。

Treap *stack[maxn];
void build(int n) {
    root = new Treap(-INF, -INF);
    stack[0] = root; int sz = 1;
    for (int i = 1; i <= n; ++i) {
        int p = sz - 1; Treap *now = new Treap(i, rand());
        while (stack[p] -> val > now -> val) stack[p--] -> maintain(); //注意到向下插入后，上面的点并没有 maintain，我们在退出的时候 maintain
        if (p != sz - 1) now -> ch[0] = stack[p + 1]; 
        stack[p] -> ch[1] = now; sz = p + 1;
        stack[sz++] = now;
    }
    while (sz) stack[--sz] -> maintain();
    root = root -> ch[1];
}

一定要记住在退栈以及最后的时候maintain！！！maintain！！！maintain！！！

Merge

对于两个相对有序的 Treap，那么 Merge 的复杂度是 $O(\log n)$ 的，否则采用启发式合并，合并两个大小为 $n, m(n\le m)$ 的 Treap 的复杂度是 $O(n\log\frac m n)$ 的，这里不介绍。
先说一说什么叫序，有两种序，一种是以值为序，即中序遍历的值递增。一种是以序列为序，即元素的相对位置，即中序遍历的值为序列（考虑字符串序列）。这两个的差别，仅仅在插入上面。Treap 可以且仅能维护一种序列。
对于以值为序，那么相对有序就是一个 Treap 的最大元素小于另一个 Treap 的最小元素。
对于以序列为序，执行 Merge 操作就是把两个序列首尾相接，自然也就默认左边的 Treap 全部小于后面的 Treap。

Treap 的合并类似左偏树和斜堆，Merge(a, b) 是一个递归操作：

如果 $a$ 为空，返回 $b$ 。
如果 $b$ 为空，返回 $a$ 。
如果 $a \rightarrow \text{val} < b \rightarrow \text{val}$ ，那么执行 a -> rc = merge(a -> rc, b), a -> maintain()。
如果 $a \rightarrow \text{val} > b \rightarrow \text{val}$ ，那么执行 b -> lc = merge(a, b -> lc), b -> maintain()。

一定要注意是 merge(a, b -> lc) 而不是 merge(b -> lc, a)，显然仍然要保证前一个 Treap 小于后一个 Treap。

Treap* merge(Treap *a, Treap *b) {
    if (a == null) return b;
    if (b == null) return a;
    if (a -> val < b -> val) {
        a -> ch[1] = merge(a -> ch[1], b);
        a -> maintain();
        return a;
    }else {
        b -> ch[0] = merge(a, b -> ch[0]);
        b -> maintain();
        return b;
    }
}

Split

对于一个 Treap，我们需要把它以第 $k$ 小拆分，那应该怎么做呢？
根据由于 Treap 具有排序二叉树的性质，左子树全部小于根，右子树全部大于根，如果第 $k$ 小在左子树，那么包含前 $k$ 小的节点不会在右子树；如果第 $k$ 小在右i子树，那么包含前 $k$ 小的节点完全包含左子树，这样就很好写递归了。
由于树高是 $\log n$ 的，所以复杂度当然也是 $\log n$ 的，这样 Treap 有了 Split 和 Merge 操作，我们可以做到提取区间，也因此可以区间覆盖，也可以区间求和等等。除此之外因为没有了旋转操作，我们还可以进行可持久化，这个下文会讲到。

typedef pair<Treap*, Treap*> Droot;
Droot split(Treap *o, int k) {
    Droot d(null, null);
    if (o == null) return d;
    if (k <= o -> ch[0] -> s) {
        d = split(o -> ch[0], k);
        o -> ch[0] = d.second;
        o -> maintain();
        d.second = o;
    }else {
        d = split(o -> ch[1], k - o -> ch[0] -> s - 1);
        o -> ch[1] = d.first;
        o -> maintain();
        d.first = o;
    }
    return d;
}

NewNode

太简单不说了。

Treap* newNode(int key) {
    pit -> key = key, pit -> val = rand(); //pit 内存池
    pit -> s = 1, pit -> ch[0] = pit -> ch[1] = null;
    return pit++;
}

可支持操作

一切可支持操作都可以通过以上四个基本操作完成：
Merge和Split可用提取区间，因此可以操作一系列区间操作
Newnode单独拿出来很必要，这样在可持久化的时候会很轻松

练习

学了数据结果总得练习一下是吧：
UVa 11922：翻转操作，以区间为序。

可持久化

所谓可持久化，就是保存历史版本，比如有 10 个版本，那么就有 10 个根，从哪个根访问，就访问的是哪个版本。可持久化的原则就是：用新建代替修改，尽量复用空间。
对于可持久化，我们可以先来看看主席树（可持久化线段树）是怎么可持久化的：由于只有父亲指向儿子的关系，所以我们可以在线段树进入修改的时候把沿途所有节点都 copy 一遍，然后把需要修改的指向儿子的指针修改一遍就好了，因为每次都是在原途上覆盖，不会修改前一次的信息。由于每次只会 copy 一条路径，而我们知道线段树的树高是 $\log n$ 的，所以时空复杂度都是 $n\log n$ 。
我们来看看旋转的 Treap，现在应该知道为什么不能可持久化了吧？如果带旋转，那么就会破环原有的父子关系，破环原有的路径和树形态，这是可持久化无法接受的。如果把 Treap 变为非旋转的，那么我们可以发现只要可以可持久化 Merge 和 Split 就可一完成可持久化。
因为上文说到了「一切可支持操作都可以通过以上四个基本操作完成」，而 Build 操作只用于建造无需理会，newNode 就是用来可持久化的工具。我们来观察一下 Merge 和 Split，我们会发现它们都是由上而下的操作！因此我们完全可以参考线段树的可持久化对它进行可持久化。
与非可持久化不同的是，我们从不修改传入的任何节点，我们只新建节点，当每次需要修改一个节点，就 newNode 出来与以前一样的做就可以了。

UVa 12538：可持久化 Treap 入门题，强制在线。

//  Created by Sengxian on 3/25/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 12538 可持久化 Treap
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <ctime>
#include <stack>
#define ls ch[0]
#define rs ch[1]
using namespace std;

int _n, _ch; bool _flag;
inline int ReadInt() {
    _n = 0, _ch = getchar(), _flag = false;
    while (!isdigit(_ch)) _flag |= _ch == '-', _ch = getchar();
    while (isdigit(_ch)) _n = (_n << 3) + (_n << 1) + _ch - '0', _ch = getchar();
    return _flag ? -_n : _n;
}

const int maxn = 50000 + 3, maxadd = 100 + 3, INF = 0x3f3f3f3f;
struct Treap *null, *pit;
struct Treap {
    int key, val, s;
    Treap *ch[2];
    Treap() {}
    Treap(int key, int val = rand()): key(key), val(val), s(1) {ch[0] = ch[1] = null;}
    void *operator new(size_t) {return pit++;}
    inline void maintain() {s = ch[0] -> s + ch[1] -> s + 1;}
}pool[4000000 + 3], *root[maxn];

inline Treap* newNode(const Treap *o) {
    if (o == null) return null;
    Treap *now = new Treap();
    *now = *o;
    return now;
}

Treap* merge(const Treap *a, const Treap *b) {
    if (a == null) return newNode(b);
    if (b == null) return newNode(a);
    if (a -> val < b -> val) {
        Treap *na = newNode(a);
        na -> rs = merge(a -> rs, b);
        na -> maintain();
        return na;
    }else {
        Treap *nb = newNode(b);
        nb -> ls = merge(a, b -> ls);
        nb -> maintain();
        return nb;
    }
}

typedef pair<Treap*, Treap*> Droot;

Droot split(const Treap *o, int k) {
    Droot d(null, null);
    if (o == null) return d;
    if (k == 0) return Droot(null, newNode(o));
    if (k == o -> s) return Droot(newNode(o), null);
    int s = o -> ls -> s;
    Treap *newroot = newNode(o);
    if (k <= s) {
        d = split(o -> ls, k);
        newroot -> ls = d.second;
        newroot -> maintain();
        d.second = newroot;
    }else {
        d = split(o -> rs, k - s - 1);
        newroot -> rs = d.first;
        newroot -> maintain();
        d.first = newroot;
    }
    return d;
}

Treap *stk[maxadd];
Treap *build(char *str) {
    Treap *root = new Treap(-INF, -INF);
    stk[0] = root; int sz = 1;
    for (int i = 0; str[i]; ++i) {
        Treap *now = new Treap(str[i]); int p = sz - 1;
        while (stk[p] -> val > now -> val) stk[p--] -> maintain();
        if (p != sz - 1) now -> ls = stk[p + 1];
        stk[p] -> rs = now; sz = p + 1;
        stk[sz++] = now;
    }
    while (sz) stk[--sz] -> maintain();
    return root = root -> rs;
}

int cntC = 0;
void print(Treap *o) {
    if (o == null) return;
    print(o -> ls);
    putchar(o -> key);
    if (o -> key == 'c') cntC++;
    print(o -> rs);
}

char a[maxadd];
int main() {
    srand(time(NULL));
    pit = pool, null = new Treap();
    null -> s = 0;
    int n = ReadInt(), cnt = 0;
    root[cnt] = null;
    for (int i = 0; i < n; ++i) {
        int oper = ReadInt();
        if (oper == 1) {
            int p = ReadInt() - cntC;
            scanf("%s", a);
            Droot l = split(root[cnt], p);
            root[++cnt] = merge(merge(l.first, build(a)), l.second);
        }else if (oper == 2) {
            int p = ReadInt() - cntC, c = ReadInt() - cntC;
            Droot l = split(root[cnt], p - 1), r = split(l.second, c);
            root[++cnt] = merge(l.first, r.second);
        }else if (oper == 3) {
            int v = ReadInt() - cntC, p = ReadInt() - cntC, c = ReadInt() - cntC;
            Droot l = split(root[v], p - 1);
            Droot r = split(l.second, c);
            print(r.first); putchar('\n');
        }else assert(false);
    }
    return 0;
}

Link Cut Tree 学习笔记 BZOJ 2132 - 圈地计划

Sengxian's Blog