平衡树之Treap 学习笔记

chlchl · 2022-03-12 15:06:39 · 个人记录

简介平衡树

平衡树全程平衡二叉搜索树，是为了解决该死的卡常 BST 问题而来的。较简单的平衡树有 3 大类：\mathrm{Treap}、\mathrm{Splay} 和替罪羊树。

其他的，比如说 AVL 树、红黑树等，要么速度过慢，要么难度偏高，知名度都不高。

本篇博客主要介绍两种 \mathrm{Treap}：旋转 \mathrm{Treap} 和 \mathrm{Fhq\ Treap}（无旋 \mathrm{Treap}）。

温馨提示：这两种 \mathrm{Treap} 没有学习优先顺序，可以先学 \mathrm{Fhq\ Treap}（也就是说你可以从下往上看）。

例题：P3369 【模板】普通平衡树。

1. 旋转 Treap

旋转 Treap（以下简称 Treap）是大多数 OIer 的入门级平衡树。但是，它涉及到的史无前例的旋转让很多人止步不前。

浅谈 Treap

Q：为什么需要旋转？
A：普通的 BST 如果数据特殊，使得它为一条链，时间复杂度会退化为 O(n^2)。我们需要通过改变 BST 的结构来保证它的时间复杂度。目前的三种方法是：旋转、分裂（下面的 Fhq_Treap）、重构（替罪羊）。Treap 采用的是旋转。

Treap，顾名思义，Tree + Heap，是树和堆的结合体。它的每个节点存有两个信息。一个是你要存的值，是可以自定义的，按照 BST 的性质排序（即左儿子比当前小，右儿子比当前大），另一个是优先级，是随机给的，按照堆的性质排序（即左右儿子大（小）于当前节点）。当然，你可以很明显地看出来，那个优先级就是为了维护平衡而生的。

为什么要随机给优先级呢？因为我们需要确保树的随机性。

下图是一棵小根堆的 Treap 树（下面的讲解都以小根堆为例），左边是自定义的 val，右边是优先级 pri：

有个概念就行了，上面的东西也不用背。

只是有一点需要注意：对于平衡树中任意一个节点 u，如图所示，它们子树大小关系一定要记住，这是后面旋转的关键！为了方便，我们将左、右儿子分别定义为 l,r，那子树的大小关系是 ll<lr<rl<rr。

如果你记牢了，准备好迎接吧！

Part 1：旋转

Treap 的旋转分为两个：左旋和右旋。由于结构对称，我将重点放在右旋，左旋放个图，各位结合右旋自行理解即可。

右旋

当新节点（设为 u）是某个节点的左儿子，且它的优先级比它爸爸大时，我们需要右旋。简单来说，是将它挪到它爸爸的位置。但是，爸爸不是瞎改的，会出现一些问题：

• 爸爸怎么办？很简单，爸爸的权值是比 u 大的，所以理应成为 u 的右儿子。这时优先级肯定是满足的（只要求“儿子大于爸爸”）；
• 这时，爸爸原来的右儿子是可以连着爸爸一起被挪走的，因为不会影响结果（这棵子树是最大的，你怎么挪都是 rr 的结构）。
• 那如果 u 原本就有右儿子咋办呐？注意了，这部分是 lr 的子树，大小介于爸爸和 u 之间。而爸爸挪完之后左儿子是空的（昔日的左儿子已经变成了如今的爸爸）。所以，我们将这棵子树改为爸爸的左儿子即可。

这样，一个完美的右旋就解决啦！总结起来三步：

1. 将爸爸的左儿子变成 u 的右儿子（挪个位置）；
2. 将 u 的右儿子变成爸爸；
3. 当前整棵树的根节点从爸爸变成 u。

注意要先挪位置再交换父子关系，不然 lr 的信息会留在 u 中，导致 u 有两个右儿子。

放个步骤图：

左旋

当新节点（设为 u）是某个节点的右儿子，且它的优先级比它爸爸大时，我们需要左旋。

大家可以跟着右旋尝试推一下左旋，我就直接放答案了，总结起来也是三步：

1. 将爸爸的右儿子变成 u 的左儿子（挪个位置）；
2. 将 u 的左儿子变成爸爸；
3. 当前整棵树的根节点从爸爸变成 u。

步骤图：

最后放两个动图，直观地理解一下：右旋、左旋。

旋转讲完了，来看看代码。

由于左右旋转是对称的，所以我们可以用一份二合一的代码，通过旋转类型（左 0 右 1）来实现两边的旋转。代码：

void update(int u){
    treap[u].sz = treap[treap[u].son[0]].sz + treap[treap[u].son[1]].sz + treap[u].cnt;
}//cnt是这个权值出现了多少次 

void rotate(int &rt, int d){//rt是未旋转前的爸爸，d是旋转类型 
    int lrson = treap[rt].son[d ^ 1];//lrson 是即将成为爸爸的节点，左旋右儿，右旋左儿 
    treap[rt].son[d ^ 1] = treap[lrson].son[d];//挪位置 
    treap[lrson].son[d] = rt;//更改父子关系 
    update(rt), update(lrson);//由于更改了结构，所以这俩的子树大小需要重新算 
    rt = lrson;//把根节点改了，rt记得加地址符 
}

最大的梦魇已经结束，下面都是一些小兵小将了。

插入

基本就是 BST 的插入。忘了没关系，结合代码很容易理解的。

在 BST 的基础上加一个判断旋转即可。代码：

void insert(int &p, int x){//p 当前节点，x 插入的权值 
    if(!p){//如果这个节点还没有 
        p = ++sum;//p 是第 ++sum 个节点 
        treap[p].sz = treap[p].cnt = 1;//次数和子树大小都是1 
        treap[p].val = x;//赋初值 
        treap[p].pri = rand();//优先级为随机数 
        return ;//以上都是新建节点，但在码量较大的题中，一般封装成newnode函数 
    }
    treap[p].sz++;//将当前子树的大小 + 1，因为 p 在当前子树中 
    if(treap[p].val == x)   treap[p].cnt++;//如果刚好相等，不用搞事了，次数+1即可 
    else if(treap[p].val < x){//如果x比当前大，往右边走 
        insert(treap[p].son[1], x);//递归~ 
        if(treap[p].pri > treap[treap[p].son[1]].pri)   rotate(p, 0);
        //如果优先级不符合要求，左旋（右子树只能左旋，不可能右旋。因为对左子树没有影响） 
    }else if(treap[p].val > x){//同理 
        insert(treap[p].son[0], x);
        if(treap[p].pri > treap[treap[p].son[0]].pri)   rotate(p, 1);
    }
    return ;
}

删除

查询某数排名

查询某排名的数

前驱 & 后继

2. Fhq Treap（非旋 Treap）

对旋转有抵触的同学们有福了，因为 Fhq Treap 不需要涉及到旋转，它是通过两个函数：Split（分裂）和 Merge（合并）来保持平衡的。

优点：

1. 不用旋转；
2. 代码短，好理解；
3. 效率高；
4. 支持可持久化（可以看我的可持久化大家族）。

Fhq Treap 的核心操作只有两个，就是分裂和合并。只要学会了这两种操作，那后面的操作就很简单了。

Split：将一棵子树根据 k 分裂。

意思是将一棵子树分成两部分：小于等于 k 分到一棵子树（设为子树 A），大于等于 k 分到另一棵子树（设为子树 B）。

例如下面这棵树根据 15 分裂后长这样（左边数值是权值，右边是优先级，下同）：

那么，到底怎么写代码呢？思路又是什么呢？

设当前点为 u，左儿子 ls，右儿子 rs。

1. 如果 u<k，那么 u 及其左子树肯定都属于 A，所以不必再往左递归，只需要往 rs 递归求出 B 即可；
2. 如果 u\geq k，那么 u 及其右子树肯定都属于 B，所以不必再往右递归，只需要往 ls 递归求出 A 即可。

但是，分裂还分两种，上面说到的是按权值分裂，即按给定的权值 k 为分界线，还有一种是按规模 k 分裂：

易见规模分裂就是将一棵树分成两部分，其中一棵子树节点个数恰好为 k（记为 A），另一棵记为 B。思路和图跟上面大同小异，只是判断变成了 sz_{ls} < k。

给出两种分裂的代码：

• 按权值分裂：

  void split(int u, int k, int &rta, int &rtb){
  //分裂后返回 rta 和 rtb，分别为两棵子树的根
  if(!u)  rta = rtb = 0;//点都找不到，别谈什么分裂了
  else{
      if(trp[u].val <= k){//注意，如果这里是小于号，则右树包含 k，否则左树包含 k
          rta = u;//小于 k 的子树根节点就是当前节点
          split(trp[u].son[1], k, trp[u].son[1], rtb);//往右子树递归
      }else{
          rtb = u;//大于等于 k 的子树根节点就是当前节点
          split(trp[u].son[0], k, rta, trp[u].son[0]);//往左子树递归
      }
      update(u);//更新 u 的子树大小
  }
  }

• 按规模分裂：

  void split(int u, int k, int &rta, int &rtb){
  if(!u){
      rta = rtb = 0;//老规矩
      return ;
  }
  pushdown(u);//下传 u 的标记（不然分裂了就啥也没有了）
  if(trp[trp[u].son[0]].sz < k){
      //如果左子节点子树大小不够，那整棵左子树都属于 A 树
      rta = u;
      split(trp[u].son[1], k - trp[trp[u].son[0]].sz - 1, trp[u].son[1], rtb);
      //在右子树补回 k-ls.sz-1 个点，凑成一棵有 k 个节点的 A 树
  }else{
      rtb = u;
      split(trp[u].son[0], k, rta, trp[u].son[0]);//否则在左子树中继续分裂
  }
  update(u);//依旧要更新 u 的sz 等信息
  }

  \mathrm{merge}：合并两棵子树

  无论是哪种分裂，合并都是一样的，只有一种版本。

假设现在你有两棵树（以上图为例子），要求你将它们合并，你要怎么才能使合并后的树平衡呢？

我们现从软柿子捏起，一步一步往前走：

如果现在有一棵子树是空的，那很明显剩下那棵子树的根节点就是合并后的根节点。

那如果两棵子树都非空，如何选择谁是爸爸呢？

相信你一定不好选。那干脆放手，随机选择！

没错，我们根据两个节点的优先级 pri 来合并。即如果 pri_{rta}<pri_{rtb}，那根节点就是 rta，否则就是 rtb。

看个图，你就懂了：

代码如下：

int merge(int rta, int rtb){//返回值是合并后的根节点 
    if(!rta || !rtb)    return rta + rtb;//如果有一棵子树为空，返回另一棵 
    pushdown(rta), pushdown(rtb);//下放标记，如果没有懒标记就可以省略 
    if(trp[rta].pri < trp[rtb].pri){//rta优先级小，rta是父亲 
        trp[rta].son[1] = merge(trp[rta].son[1], rtb);
        //新的右儿子就是右儿子和rtb合并后的根节点 
        update(rta);//更新 
        return rta;//返回 
    }else{
        trp[rtb].son[0] = merge(rta, trp[rtb].son[0]);//同上 
        update(rtb);
        return rtb;
    }
}

了解完这两个操作，Fhq_treap 就讲完了。

什么？你问我剩下的操作？直接乱搞啊！

好吧，乱搞是不行的，但 Fhq_treap 的其余操作真的及其简短，前无古人，估计后也无来者。

只放 P3369 代码 + 注释，结合理解叭！

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, sum, rt;
struct Fhq_Tree{
    int val, pri, sz, son[2];
} trp[N];

int newnode(int v){
    trp[++sum].sz = 1, trp[sum].val = v;
    trp[sum].pri = rand();//优先级赋随机数 
    return sum;
}

void update(int u){
    trp[u].sz = trp[trp[u].son[0]].sz + trp[trp[u].son[1]].sz + 1;
}//本题只要更新 sz 

void split(int u, int k, int &rta, int &rtb){
    //分裂后返回 rta 和 rtb，分别为两棵子树的根
    if(!u)  rta = rtb = 0;//点都找不到，别谈什么分裂了
    else{
        if(trp[u].val <= k){
            rta = u;//小于 k 的子树根节点就是当前节点
            split(trp[u].son[1], k, trp[u].son[1], rtb);//往右子树递归
        }else{
            rtb = u;//大于等于 k 的子树根节点就是当前节点
            split(trp[u].son[0], k, rta, trp[u].son[0]);//往左子树递归
        }
        update(u);//更新 u 的子树大小
    }
}

int merge(int rta, int rtb){
    if(!rta || !rtb)    return rta + rtb;
    if(trp[rta].pri < trp[rtb].pri){
        trp[rta].son[1] = merge(trp[rta].son[1], rtb), update(rta);
        return rta;
    }else{
        trp[rtb].son[0] = merge(rta, trp[rtb].son[0]), update(rtb);
        return rtb;
    }
}

void insert(int v){
    int rta, rtb;
    split(rt, v, rta, rtb);//按权值 v 分裂 
    rt = merge(merge(rta, newnode(v)), rtb);
    //新建 v 后与 A 合并，再整体与 B 合成一棵完整的树 
}

void del(int v){//要删的点权值是 v 
    int x, y, z;
    split(rt, v, x, z);//按 v 分裂，x 是A树根，z是B树根 
    split(x, v - 1, x, y);
    //将A按v-1分割，此时A拆分成了左子树和中子树 m（介于A和B之间） 
    //使得 m 的所有结点的 val 均等于 v 
    y = merge(trp[y].son[0], trp[y].son[1]);//合并m根节点的左右儿子，等于删掉了 v 
    rt = merge(merge(x, y), z);//最后合并三棵树 
}

int rnk(int k){
    int x, y, ans;
    split(rt, k - 1, x, y);//按照k-1分裂 
    ans = trp[x].sz + 1;//k的排名就是<k的数的个数+1 
    rt = merge(x, y);
    return ans;
}

int kth(int u, int k){//查询排名为 k 的数，这个没什么好方法，按老套路 
    while(1){
        if(k <= trp[trp[u].son[0]].sz)  u = trp[u].son[0];
        else if(k == trp[trp[u].son[0]].sz + 1) return u;
        else    k -= trp[trp[u].son[0]].sz + 1, u = trp[u].son[1];
    }
}

int pre(int k){//求 k 的前驱 
    int x, y, ans;
    split(rt, k - 1, x, y);//按k-1分裂 
    ans = trp[kth(x, trp[x].sz)].val;//在A树中排名为sz，即最大的数就是k前驱 
    rt = merge(x, y);
    return ans;
}

int nxt(int k){
    int x, y, ans;
    split(rt, k, x, y);
    ans = trp[kth(y, 1)].val;//在B树中排名为1，即最小的数就是k后继 
    rt = merge(x, y);
    return ans;
}

int main(){
    srand(time(0));
    scanf("%d", &n);
    while(n--){
        int x, op;
        scanf("%d%d", &op, &x);
        if(op == 1) insert(x);
        else if(op == 2)    del(x);
        else if(op == 3)    printf("%d\n", rnk(x));
        else if(op == 4)    printf("%d\n", trp[kth(rt, x)].val);
        else if(op == 5)    printf("%d\n", pre(x));
        else if(op == 6)    printf("%d\n", nxt(x));
    }
    return 0;
}

Fhq_treap 区间操作

Fhq_treap 能够执行所有 Splay 能执行的区间操作，是 Splay 的首选代替品。我们用一道谷外的毒瘤例题进行讲解：\mathrm{SuperMemo}。

这道题是一道难得的高质量题目。我们一个一个操作来分析。

Fhq_treap 区间操作时，我们的思路与 Splay 相似，将 \lbrack1,l-1\rbrack 的和 \lbrack r+1,n\rbrack 的分裂出来，那中间那棵子树就是 \lbrack l,r \rbrack，就可以为所欲为进行操作了。

基本函数

比较简单，包括下放标记、更新子树。

#define ls(u) (trp[u].son[0])
#define rs(u) (trp[u].son[1])//宏定义可以帮助你节省不少码量

int newnode(int val){
    ++tot;
    trp[tot].val = trp[/*++*/tot].mn = val;//如果想在这一行++tot，要在打注释的地方，不能在前面的val，因为赋值语句是从右往左的啊！
    trp[tot].sz = 1;
    trp[tot].pri = rand();
    return tot;
}

void update(int u){
    trp[u].sz = trp[ls(u)].sz + trp[rs(u)].sz + 1;
    trp[u].mn = trp[u].val;
    if(ls(u))   trp[u].mn = min(trp[u].mn, trp[ls(u)].mn);//求区间 min 值 
    if(rs(u))   trp[u].mn = min(trp[u].mn, trp[rs(u)].mn);//要判断儿子是否存在，不然最小值一直都是 0 
}

Pushdown

为什么要单拎出来讲？因为我卡得最长时间的就是它了（原本一直以为是 revolve 的问题，但是后来发现没有 revolve 的数据也错了）。

维护值的 pushdown 没啥好说的，关键是这个翻转标记的下传，目前有两种写法。

一种是：翻转时直接标记，pushdown 时交换左右儿子并下传；另一种是：翻转时标记 + 交换左右儿子，pushdown 时交换左右儿子的左右儿子，并下传标记。

一句话，翻转时交不交换左右儿子？

交换。两者在文艺平衡树一题中可顺利通过，但在本题中，第一种做法是不行的。具体原因我还没找到，但我猜测是如果不立刻交换，最后查询的时候数据又巧妙地避开了一次 pushdown，就会导致最下面一层的左右儿子没有交换。

void addnode(int u, int v){trp[u].taga += v, trp[u].mn += v, trp[u].val += v;}//这种更新一个节点比较多的建议单独写函数，debug也方便

void revson(int u){swap(trp[u].son[0], trp[u].son[1]), trp[u].tagr ^= 1;}

void pushdown(int u){//下放的内容是两个标记 
    if(!u)  return ;
    int ls = ls(u), rs = rs(u);
    if(trp[u].taga){
        if(ls)  addnode(ls, trp[u].taga);
        if(rs)  addnode(rs, trp[u].taga);
        trp[u].taga = 0;
    }
    if(trp[u].tagr){
        if(ls)  revson(ls);
        if(rs)  revson(rs);
        trp[u].tagr ^= 1;//=0也没毛病哈
    }
}

分裂与合并

因为是区间操作，涉及到的操作基本都是下标，所以我们用规模分裂。

void split(int u, int k, int &rta, int &rtb){
    if(!u){
        rta = rtb = 0;
        return ;
    }
    pushdown(u);//记得pushdown 
    if(trp[ls(u)].sz < k){
        rta = u;
        split(rs(u), k - trp[ls(u)].sz - 1, trp[rta].son[1], rtb);
    }else{
        rtb = u;
        split(ls(u), k, rta, trp[rtb].son[0]);
    }
    update(u);
}

int merge(int rta, int rtb){
    if(!rta || !rtb)    return rta + rtb;
    pushdown(rta), pushdown(rtb);//记得两个都要pushdown！ 
    if(trp[rta].pri < trp[rtb].pri){
        trp[rta].son[1] = merge(trp[rta].son[1], rtb);
        update(rta);
        return rta;
    }else{
        trp[rtb].son[0] = merge(rta, trp[rtb].son[0]);
        update(rtb);
        return rtb;
    }
}//不解释了，不会的再看看上面的讲解吧

区间加（add）

简短得不能再简短，代码注释说的很清楚了，如果看懂了分裂的原理那应该能看懂叭：

void add(int l, int r, int v){
    int x, y, z;
    split(rt, l - 1, x, y);//x 此时规模是 l-1，y此时就是 n-l-1 
    split(y, r - l + 1, y, z);//在y中再分 r-l+1 个树，z就是l+1~n的区间，y就是要操作的数 
    trp[y].taga += v, trp[y].mn += v, trp[y].val += v;//将懒标记、最小值和当前节点的值+v 
    rt = merge(x, merge(y, z));//合并后根节点赋给 rt 
}

区间翻转

细心的你会发现，反转 \lbrack l,r\rbrack 就是将存储 \lbrack l,r\rbrack 的那棵子树交换左右儿子（这个感性理解，应该很好懂吧）。我们采用懒标记的方式标记，改变结构时再进行下传（所以 pushdown 函数中 tagr 那里有一句 swap）。

void reverse(int l, int r){
    int x, y, z;
    split(rt, l - 1, x, y);
    split(y, r - l + 1, y, z);//分裂出区间
    revson(y);//这个函数pushdown时已经出现过啦！
    rt = merge(x, merge(y, z));//合并 
}

区间循环移位

这个操作巨恶心，交了好多次都是这里害的。

插入（在指定位置后插入）

这个就非常简单了，按 u 分裂之后直接合并就好了。

删除

上面是删除 x，这里是删除 A_x。稍有不同，但是由于分裂形式不同，所以思路和代码大同小异。

查询最小值

这简直就是无脑操作。分裂区间后直接返回根节点 val 就好了。

好了，讲完了，放代码：

代码不长，后来加上了注释，添加了宏定义、改了下变量名，从 4299 B 直降到 3987 B，还是不错的。