FHQ Treap

讲完了treap和splaytree，接下来讲把这两的思想混合在一起的 FHQ Treap，据说作者是范浩强。

splay其实还有两个操作split和merge没有介绍，我打算把这两放在这里一并介绍

Split和Merge

Split就是把树按某个条件划分成两棵子树，如果是查找树，就按某个值划分为小于它的以及大于等于它的（等于号取哪边怎么好写怎么来就是），如果是序列维护，那就按照rank来划分。而merge操作则正好相反，把两棵子树合并成为一棵。所以，如果我们需要对某个区间做操作，那么我们就把那个区间Split出来，操作好了后（打懒惰标记，或取出结果）再Merge回去就行了，与splay操作的思路是差不多的。不过为了在split再merge后能间接对树的平衡性优化，我们不能简单地merge，要套用Treap的随机数法，我们先来看怎么split。

先定义好接口void split(int tp, int k, int &x, int &y)，x是返回的左子树，y是返回的右子树，接着我们需要递归split，如果划分点在左子树，那么y一定是根，反之划分点在右子树，那么x一定是根。确定了其中一个，在递归调用的时候，假如y确定了，于是还没确定的，就是x以及根节点的左子树的指向，所以把这两传参就行了，时间复杂度 $O(logn)$ ，具体代码如下：

// 维护序列的实现
void split(int tp, int k, int &x, int &y)
{
    if (!tp) { x = y = 0; return; }
    pushdown(tp);
    if (k <= nodes[ch(tp, 0)].sz)
    {
        y = tp;
        split(ch(tp, 0), k, x, ch(tp, 0));
        update(y);
    }
    else
    {
        x = tp;
        split(ch(tp, 1), k - nodes[ch(tp, 0)].sz - 1, ch(tp, 1), y);
        update(x);
    }
}

接下来讲讲merge，我们不能直接把右子树直接接在左子树的最后一个元素后，这样会导致树高度太大。在Treap里面，引入了一个随机值，来决定谁来做根节点，所以，我们就对比这个值，如果左子树的小，那么就让左子树的右儿子与右子树merge，否则就让右子树的左儿子与左子树merge，递归调用就是了，时间复杂度 $O(logn)$

int merge(int tl, int tr)
{
    if (!tl) return tr;
    else if (!tr) return tl;
    if (nodes[tl].k < nodes[tr].k)
    {
        pushdown(tl);
        ch(tl, 1) = merge(ch(tl, 1), tr);
        return update(tl);
    }
    else
    {
        pushdown(tr);
        ch(tr, 0) = merge(tl, ch(tr, 0));
        return update(tr);
    }
}

基本模板

这么快就给模板了？没错，你在理解了Treap以后，再去学习FHQ-Treap那是相当简单的，最复杂的两个操作已经讲完了，相比Treap，它不需要旋转操作，而通过merge操作来让树平衡，而且这组操作让其它的操作相比Treap都来得简单，最不容易写出BUG，代码也是最短的一个，常数也比splaytree小，所有操作的期望时间复杂度都是 $O(logn)$ 。

template<typename T>
struct FHQ_Treap
{
    struct data
    {
        T v;
        data(int _v = 0) :v(_v) {}
        data operator + (const data& d) const
        {
            data r;
            r.v = v + d.v;
            return r;
        }
        data operator * (int t) const
        {
            data r;
            r.v = v * t;
            return r;
        }
        operator bool() const { return v != 0; }
        operator T() const { return v; }
    };
    struct node
    {
        int ch[2], sz;
        unsigned k;
        data d, sum, lz_add;
        node(int z = 1) :sz(z), k(rnd()) { ch[0] = ch[1] = 0; }
        static unsigned rnd()
        {
            static unsigned r = 0x123;
            r = r * 69069 + 1;
            return r;
        }
    };
    vector<node> nodes;
    int root;
    int recyc;
    int reserve_size;
    void reserve()
    {
        if (size() >= reserve_size)
            nodes.reserve((reserve_size *= 2) + 1);
    }
    inline int& ch(int tp, int r) { return nodes[tp].ch[r]; }
    int new_node(const data& d)
    {
        int id = (int)nodes.size();
        if (recyc)
        {
            id = recyc;
            if (ch(recyc, 0) && ch(recyc, 1))
                recyc = merge(ch(recyc, 0), ch(recyc, 1));
            else
                recyc = ch(recyc, 0) ? ch(recyc, 0) : ch(recyc, 1);
            nodes[id] = node();
        }
        else nodes.push_back(node());
        nodes[id].d = d;
        nodes[id].sum = d;
        return id;
    }
    int update(int tp)
    {
        node& n = nodes[tp];
        n.sz = 1 + nodes[n.ch[0]].sz + nodes[n.ch[1]].sz;
        n.sum = n.d + nodes[n.ch[0]].sum + nodes[n.ch[1]].sum;
        return tp;
    }
    void add(int tp, const data& d)
    {
        node& n = nodes[tp];
        n.lz_add = n.lz_add + d;
        n.d = n.d + d;
        n.sum = n.sum + d * n.sz;
    }
    void pushdown(int tp)
    {
        node& n = nodes[tp];
        if (n.lz_add)
        {
            add(n.ch[0], n.lz_add); add(n.ch[1], n.lz_add);
            n.lz_add = 0;
        }
    }
    int merge(int tl, int tr)
    {
        if (!tl) return tr;
        else if (!tr) return tl;
        if (nodes[tl].k < nodes[tr].k)
        {
            pushdown(tl);
            ch(tl, 1) = merge(ch(tl, 1), tr);
            return update(tl);
        }
        else
        {
            pushdown(tr);
            ch(tr, 0) = merge(tl, ch(tr, 0));
            return update(tr);
        }
    }
    void split(int tp, int k, int &x, int &y)
    {
        if (!tp) { x = y = 0; return; }
        pushdown(tp);
        if (k <= nodes[ch(tp, 0)].sz)
        {
            y = tp;
            split(ch(tp, 0), k, x, ch(tp, 0));
            update(y);
        }
        else
        {
            x = tp;
            split(ch(tp, 1), k - nodes[ch(tp, 0)].sz - 1, ch(tp, 1), y);
            update(x);
        }
    }
    void remove(int& tp)
    {
        if (recyc == 0) recyc = tp;
        else recyc = merge(recyc, tp);
        tp = 0;
    }
    // interface
    void init(int size)
    {
        nodes.clear();
        nodes.reserve((size = max(size, 15)) + 1);
        nodes.push_back(node(0));
        root = 0;
        recyc = 0; reserve_size = size + 1;
    }
    T get(int id) { return nodes[id].d; }
    int size() { return nodes[root].sz; }
    int kth(int k)
    {
        int x, y, z;
        split(root, k, y, z); split(y, k - 1, x, y);
        int id = y;
        root = merge(merge(x, y), z);
        return id;
    }
    void insert(int k, data v)
    {
        int l, r;
        split(root, k - 1, l, r);
        int tp = new_node(v);
        root = merge(merge(l, tp), r);
    }
    void erase(int l, int r)
    {
        int x, y, z;
        split(root, r, y, z); split(y, l - 1, x, y);
        remove(y);
        root = merge(x, z);
    }
    void range_add(int l, int r, data v)
    {
        int x, y, z;
        split(root, r, y, z); split(y, l - 1, x, y);
        add(y, v);
        root = merge(merge(x, y), z);
    }
    T getsum(int l, int r)
    {
        int x, y, z;
        split(root, r, y, z); split(y, l - 1, x, y);
        T ret = nodes[y].sum;
        root = merge(merge(x, y), z);
        return ret;
    }
};

以上是个支持区间加、区间删和区间求和的模板。除了LCT，都交给这个数据结构解决吧。

其它问题

如果你要问为什么不一开始就介绍这个，而先解释其它的树结构，那是因为那是基础啊，基础搞好了，那再搞这个就很简单了。