\(fhq~~treap\) 总结

​ \(fhq~Treap\) 是一种很好用的数据结构。它很像 $ Treap$ ，但它也可以支持区间操作，同时它也可以进行可持久化，它甚至还很好写。面对这么好的数据结构，怎么能不学一学呢？

​ 这个ppt可能是起源？

​ 如果你已经看过了上面那个 \(ppt\)，应该知道无旋 \(Treap\) 的思想是不修改，只新建和重用。下面以这道题为背景，讲一下无旋 \(Treap\) 的写法。

\(split\)

​ 首先它有一个有趣的操作 \(split\)，意思是把一棵树分裂成两棵树。嗯...？其实相当于新建两棵树，它们拼起来等于原来那棵树。两种说法有区别吗？当然有啦，注意，“不修改！“，如果直接把树变成两棵，显然就是修改了，而用两棵新的树表示它，对它并没有什么影响。这里可能说的有点啰嗦了，但是我认为对于后面的理解还是有好处的。不过，分裂后可能确实会对原树进行一些更改，但是并不影响它二叉搜索树的性质。

​ 分裂也有两种：

​ 1、将权值小于等于k的节点分裂出来。

void split (int n,int k,int &x,int &y)
{
    if(!n) { x=y=0; return; }
    if(v[n]<=k) x=n,split(ch[x][1],k,ch[x][1],y);
    else y=n,split(ch[y][0],k,x,ch[y][0]);
    update(n);
}

​ 2、将前k个节点分裂出来。

void split (int n,int k,int &x,int &y)
{
    if(!n) { x=y=0; return; }
    if(d[n]) pushdown(n);
    if(s[ ch[n][0] ]<k)
        x=n,split(ch[x][1],k-s[ ch[x][0] ]-1,ch[x][1],y);
    else
        y=n,split(ch[y][0],k,x,ch[y][0]);
    update(n);
}

​ 第一个主要用于维护数集，第二个主要用于维护序列。

\(merge\)

​ 字面意思，就是把两棵树合并。不过这个操作限制挺多的，要求某一棵树完全小于另一树，也就是说，在不考虑随机权值的情况下可以随便合并。为了维护平衡，我们按照随机权值来合并。看代码：

int mer (int x,int y)
{
    if(!x||!y) return x|y;
    if(r[x]<r[y])
    {
        ch[x][1]=mer(ch[x][1],y);
        update(x); return x;
    }
    else
    {
        ch[y][0]=mer(x,ch[y][0]);
        update(y); return y;
    }
}

\(insert\)

​ 剩下的操作真是一个比一个简单。如何插入？首先把小于它的分裂出来命名为 \(a\) ，剩下的命名为 \(b\)，然后给它新建一个节点 \(c\)，最后 \(rt=mer(mer(a,b),c)\)；

\(delete\)

​ 小于它的分出来，大于它的分出来，等于它的随便删一个，再按顺序 \(merge\) 回来；

\(rank\)

​ 比它小的分出来，查一下 \(size\) 再 +1；

\(kth\)

​ 如果无聊的话，可以尝试分裂前 \(k\) 大，然而直接在树上走着找就可以了，因为树高是 \(log\) 的；

\(pre\)

​ 比它小的分裂出来，查询最大的那个数；

\(nex\)

​ 比它大的分裂出来，查询最小的那个数；

​