FHQ Treaplyh's blog

        本文介绍fhq Treap的相关内容，是Treap（树堆）的延伸。
        另外本文仅涉及普通平衡树和文艺平衡树的内容，暂不涉及可持久化平衡树，关于可持久化会有单独的文章（以后更新）。

        fhq Treap是非旋的树堆，具有易实现，功能强大的优点，支持可持久化和文艺平衡树操作。
        fhq Treap中允许有相同权值的两个结点，因此每个结点不再有标记数量的s，也可以理解成每个结点的s一定为1。此时BST可以定义为左子树结点的值都不大于该结点，右子树都不小于该结点。
        在上一篇文章中提到了Treap（树堆）的原理：利用优先级的随机性来保持树结构的随机性。fhq Treap是非旋的树堆，它自然没有旋转操作，而有另外的两个核心操作：分离（split）和合并（merge）。

分离操作

分离是指将一个treap分成两个treap，常用的分离标准有两种：按值分离和按数量分离。

按值分离

        按值分离常常用于普通平衡树（普通平衡树就是上一篇文章提到的那些操作）。给定一个值val，需要将treap分离成两个，其中一个树中所有点权值都不大于val（称树a），另一个全都大于val（称树b）。
        假如现在需要分离以rt结点为根的treap，分离后的treap的根是a和b（a和b一开始是未赋值的）。如果rt的权值不大于val，说明rt结点应该在树a中，容易知道rt结点的左子树也应该在树a中，那么不妨将rt作为树a的根结点。此时rt结点及其左子树已经得到了“归属”，下面的问题就是求树b的根，求树a的右子树，于是继续分离rt结点的右子树，这是一个递归过程。
        于是就可以得到下面的分离代码：

void split(int rt, int &a, int &b, int v) {
    if (rt == 0) {//不需分离时，a和b都是空树
        a = b = 0;
        return;
    }
    if (node[rt].v <= v)a = rt, split(node[rt].ch[1], node[a].ch[1], b, v);
    else b = rt, split(node[rt].ch[0], a, node[b].ch[0], v);
    update(rt);
}

这就是分离的函数实现，注意最后需要更新rt的num。split函数巧妙地利用了引用使得代码十分优雅。
容易看出分离过程不会破坏BST的性质和堆的性质。

按数量分离

给定数量v，将treap中前v小的数分离到树a中，其余分离到树b中，这就是按数量分离。为什么还要学按数量分离呢？因为这是文艺平衡树的关键实现原理。
和按值分离原理类似。假设现在需要分离以rt为根的treap，如果rt左子树的结点数量（由于s为1，故结点数量就是数的数量）小于v，那么易知rt结点及其左子树都应该分到树a中，然后进行递归分离。如果左子树结点数量不小于v，那么rt结点及其右子树应该分到树b中。

void split(int rt, int &a, int &b, int v) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (node[node[rt].ch[0]].num < v)a = rt, split(node[rt].ch[1], node[a].ch[1], b, v - node[node[rt].ch[0]].num - 1);
    else b = rt, split(node[rt].ch[0], a, node[b].ch[0], v);
    update(rt);
}

这里有一处需要注意：在分离右子树时，v需要进行更新。

合并操作

        合并操作就是将树a和树b合并为一个treap，合并操作有一个前提：树a中的所有值不能大于树b中的值。无论采用按值分离方法还是按数量分离方法都是满足这个条件的。
        由于树b上的数一定不小于树a，那么也不小于树a的根结点，那么合并a和b的问题就是把b合并到a的右子树上。当然也可以选择把a合并到b的左子树上，这于是就是一个递归问题。
        选择任何一个都可以吗？显然不是，因为还要满足堆的性质。两棵树都是满足堆的性质的，此时如果树a的根节点优先级更高，则应合并a的右子树和b，否则合并b的左子树和a。

void merge(int &rt, int a, int b) {//rt是合并后的树根
    if (a == 0 || b == 0) {//其中任何一个为0直接赋值即可
        rt = a + b;//赋值不为0的那一个，这是一处巧妙的写法
        return;
    }
    if (node[a].key > node[b].key)rt = a, merge(node[rt].ch[1], node[a].ch[1], b);
    else rt = b, merge(node[rt].ch[0], a, node[b].ch[0]);
    update(rt);
}

插入元素

有了split和merge就可以很容易地实现插入、删除操作。
要插入值为val的点，需要先新建一个值为val的点，假设新结点编号为p。在原treap上按val的值进行分离，分离成不大于val的treap和大于val的treap，然后合并树a和p，再合并树a和树b即可。

int addNode(int x) {//分配新结点编号
    node[++cnt].v = x, node[cnt].ch[0] = node[cnt].ch[1] = 0;
    node[cnt].num = 1, node[cnt].key = rand();
    return cnt;
}
void insert(int x) {//插入元素
    int p = addNode(x), a, b;
    split(root, a, b, x);
    merge(a, a, p);
    merge(root, a, b);
}

删除元素

将原treap按val值分离成树a和树b，再将树a按值val-1分离成树c和树d。这样树d就是由全体val值结点组成的，合并树d的左子树和右子树（相当于删除根结点），再与树c和树b合并即可。

void delNum(int x) {
    int a, b, c;//这里没有建变量d，为了重用变量
    split(root, a, b, x);//分离root产生树a和树b
    split(a, a, c, x - 1);//分离a产生a和c（重用变量a）
    merge(c, node[c].ch[0], node[c].ch[1]);//合并c的左右子树到c中
    merge(a, a, c);//将c合并到a中
    merge(root, a, b);//将a、b合并到root中
}

之后的操作（如查找前驱后继等等）与普通treap相比没有变化。这里提供一种递归版求解方法，更加优雅：

int findRank(int rt, int x) {//查找排名
    if (rt == 0)return 1;
    if (node[rt].v < x)return node[node[rt].ch[0]].num + 1 + findRank(node[rt].ch[1], x);
    return findRank(node[rt].ch[0], x);
}

int findNum(int rt, int x) {//根据排名找数
    if (node[node[rt].ch[0]].num + 1 == x)return node[rt].v;
    if (node[node[rt].ch[0]].num + 1 < x)return findNum(node[rt].ch[1], x - node[node[rt].ch[0]].num - 1);
    return findNum(node[rt].ch[0], x);
}

int findPre(int rt, int x) {//查找前驱
    if (rt == 0)return -0x7fffffff;
    if (node[rt].v >= x)return findPre(node[rt].ch[0], x);
    return max(findPre(node[rt].ch[1], x), node[rt].v);
}

int findNext(int rt, int x) {//查找后继
    if (rt == 0)return 0x7fffffff;
    if (node[rt].v <= x)return findNext(node[rt].ch[1], x);
    return min(findNext(node[rt].ch[0], x), node[rt].v);
}

        下面介绍fhq Treap的另一个功能：文艺平衡树。有洛谷模板题。
        所谓文艺平衡树就是实现这样一个功能：给定一个区间，不断翻转其中的某一段子区间，求最后的区间序列。
        当我们需要翻转[l,r]区间时，首先按数量分离原有treap，分离成[1,l-1]、[l,r]、[r+1,n]三段区间，然后给[l,r]打上翻转标记，再将它们合并。
        翻转标记如同线段树中的lazy标记，表示以这个点为根的树需要翻转，该标记仅有0和1两种取值。它同时也有down函数来完成下压标记操作：

inline void down(int x) {
    swap(node[x].ch[0], node[x].ch[1]);//交换左右子树
    node[node[x].ch[0]].lazy ^= 1;//打上标记
    node[node[x].ch[1]].lazy ^= 1;
    node[x].lazy = 0;//清空标记
}

这样我们的split和merge函数也应该带上下压操作：

void split(int rt, int &a, int &b, int v) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (node[rt].lazy)down(rt);//下压标记
    if (node[node[rt].ch[0]].num < v)a = rt, split(node[rt].ch[1], node[a].ch[1], b, v - node[node[rt].ch[0]].num - 1);
    else b = rt, split(node[rt].ch[0], a, node[b].ch[0], v);
    update(rt);
}

void merge(int &rt, int a, int b) {
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (node[a].key > node[b].key) {
        if (node[a].lazy)down(a);//下压标记
        rt = a, merge(node[a].ch[1], node[a].ch[1], b);
    } else {
        if (node[b].lazy)down(b);//下压标记
        rt = b, merge(node[b].ch[0], a, node[b].ch[0]);
    }
    update(rt);
}

        问题来了：交换左右子树难道不会违反BST性质？答案是肯定会违反的，但我们应该从一个更高的高度去理解BST。
        BST左子树权值不大于该结点实质上是左子树结点的权重不大于该结点，权值不一定代表权重。因此翻转左右子树实质上就是认为左右结点的权重发生了调换。我们的merge函数和按数量分离的split函数不会改变原有的权重关系，而不是权值关系，因此翻转后再进行split或者merge等操作并不会影响翻转的结果。
        但容易看出，按值分离函数是按照权值关系进行的，所以在文艺平衡树进行中不能有按值分离操作。
        输出最后的结果相当容易，只需一次中序遍历即可，记得下压标记：

void print(int x) {
    if (!x)return;
    if (node[x].lazy)down(x);
    print(node[x].ch[0]);
    cout << node[x].v << " ";
    print(node[x].ch[1]);
}

        扩展：洛谷模板题中原有的序列是1~n，这个序列很特殊以至于我们可以先插入这几个元素再按文艺平衡树进行操作。但是如果原有序列是随机的呢？由于插入操作需要按值分离split函数，这个函数基于权值关系，插入后原有序列关系就被打乱了。洛谷模板题之所以可以直接插入是因为权值正好就是权重。
        一种方法是构造1~n到原有序列的映射，再将1~n插入treap中，进行区间操作，输出时映射回来即可。
        下附洛谷模板题AC代码：

#include<bits/stdc++.h>

using namespace std;

struct Node {
    int ch[2], v, num, key, lazy;

    Node() : num(0) {
        lazy = ch[0] = ch[1] = 0;
    }
} node[100005];

int root = 0, cnt = 0;

inline void update(int x) {
    node[x].num = node[node[x].ch[0]].num + node[node[x].ch[1]].num + 1;
}

inline int addNode(int x) {
    node[++cnt].v = x, node[cnt].ch[0] = node[cnt].ch[1] = 0;
    node[cnt].num = 1, node[cnt].key = rand();
    return cnt;
}

inline void down(int x) {
    swap(node[x].ch[0], node[x].ch[1]);
    node[node[x].ch[0]].lazy ^= 1;
    node[node[x].ch[1]].lazy ^= 1;
    node[x].lazy = 0;
}

void split(int rt, int &a, int &b, int v) {//按数量分离
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (node[rt].lazy)down(rt);
    if (node[node[rt].ch[0]].num < v)a = rt, split(node[rt].ch[1], node[a].ch[1], b, v - node[node[rt].ch[0]].num - 1);
    else b = rt, split(node[rt].ch[0], a, node[b].ch[0], v);
    update(rt);
}

void merge(int &rt, int a, int b) {
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (node[a].key > node[b].key) {
        if (node[a].lazy)down(a);
        rt = a, merge(node[a].ch[1], node[a].ch[1], b);
    } else {
        if (node[b].lazy)down(b);
        rt = b, merge(node[b].ch[0], a, node[b].ch[0]);
    }
    update(rt);
}

void solve(int l, int r) {//翻转函数
    int a, b, c;
    split(root, a, b, l - 1);
    split(b, b, c, r - l + 1);
    node[b].lazy ^= 1;
    merge(a, a, b), merge(root, a, c);
}

void split2(int rt, int &a, int &b, int v) {//按值分离
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (node[rt].v <= v)a = rt, split2(node[rt].ch[1], node[a].ch[1], b, v);
    else b = rt, split2(node[rt].ch[0], a, node[b].ch[0], v);
    update(rt);
}


inline void insert(int x) {//插入
    int p = addNode(x), a, b;
    split2(root, a, b, x);
    merge(a, a, p);
    merge(root, a, b);
}

void print(int x) {//输出
    if (!x)return;
    if (node[x].lazy)down(x);
    print(node[x].ch[0]);
    cout << node[x].v << " ";
    print(node[x].ch[1]);
}

int main() {
    ios::sync_with_stdio(false);
    srand(static_cast<unsigned int>(time(nullptr)));
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)insert(i);//把1~n插入到treap中
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        solve(x, y);
    }
    print(root);
    return 0;
}