平衡树三讲——ylxmf2005的OI教程

前置芝士 & 前言

  1. 线段树(如果会可持久化线段树更好)
  2. 树的相关芝士
  3. 普及组一等以上的码力。
  4. 耐心

本文章会讲解下面内容:

  1. 普通平衡树
  2. 文艺平衡树
  3. 可持久化文艺平衡树

本文章的所有平衡树,都是用 FHQ Treap 实现的。

普通平衡树

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

  1. 插入 $x$ 数
  2. 删除 $x$ 数(若有多个相同的数,因只删除一个)
  3. 查询 $x$ 数的排名(排名定义为比当前数小的数的个数 $+1$。若有多个相同的数,因输出最小的排名)
  4. 查询排名为 $x$ 的数
  5. 求 $x$ 的前驱(前驱定义为小于 $x$,且最大的数)
  6. 求 $x$的后继(后继定义为大于 $x$,且最小的数)

平衡树是什么?能吃吗?不能吃就不学了。

平衡树,本质上就是一棵二叉查找树,二叉查找树呢有一个非常好的性质:左儿子的值比父亲的小,右儿子的值比父亲大。那么,为什么不叫二叉搜索树,却偏偏叫平衡树呢?比如,某毒瘤出题出了这样的数据:

5
1 2 3 4 5

那么建出二叉搜索树一般长成这样子:

《平衡树三讲——ylxmf2005的OI教程》

我们发现,他退化成了一条链。这样每次操作都会成为 $O(n)$ 的。

平衡树就可以解决这个问题了,我们下面讲的是如何用 FHQ Treap 来解决。

$\text{FHQ Treap = Tree + Heap}$

Treap 通过给节点赋一个随机数,当作这个点的优先级,通过随机化让平衡树尽可能的平衡。你没听错,就是随机数。令人惊喜的是,FHQTreap 的中序遍历能得到原来的序列。那么,我们应该如何维护 Treap 呢?

存储

我们需要以下变量来存储:

struct FHQTreap{
    int ch[N][2] /*0为左儿子 1为右儿子*/ , val[N] /*节点的值*/ , key[N] /*节点的优先级*/, siz[N] /* 以该节点为根的子树的大小(包括它本身)*/, root /*树的根*/, cnt /*节点个数*/;
} T;

信息上传

我们在进行一些操作的时候,可能要将儿子的信息传到父亲身上。

inline void PushUp(re int rt) {
    siz[rt] = siz[ch[rt][0]] + siz[ch[rt][1]] + 1; //以左儿子为根的子树+右儿子为根的子树+它本身即为1 
}

新建节点

新建一个节点。

inline int NewNode(re int v) {// v 为新建的节点的值
    siz[++cnt] = 1; val[cnt] = v; key[cnt] = rand()/*随机一个优先级*/;
    return cnt;
}

合并子树

重要的操作,合并两个子树。

我们要按照优先级来合并两个子树,我们这里规定,如果子树 $x$ 的优先级比 $y$ 高($key_x < key_y$),那么我们将子树 $y$ 合并到子树 $x$ 的右儿子上。否则,我们将子树 $x$ 合并到子树 $y$ 的左儿子上。合并之后,需要把改变后的信息上传到父节点。

int Merge(re int x, re int y) {//将x和y合并返回合并后的子树的编号
        if (!x || !y) return x + y;//如果有任何一个子树为空,那么返回另一个(如果两个都是空返回0)
        if (key[x] < key[y]) {
            ch[x][1] = Merge(ch[x][1], y);
            PushUp(x); return x;
        } else {
            ch[y][0] = Merge(x, ch[y][0]);
            PushUp(y); return y;
        }
    }

分裂子树

和合并子树一样重要,我们有两种分裂方法:一个是根据权值分,另一个是根据大小分。这道题最方便的方法是用权值分,大小分下面会讲。

用权值怎么分呢?我们可以将所有点权小于等于传入的参数的点分裂到左子树,其他的分裂到右子树。递归求解即可,最后我们将分裂后子树的信息上传。

void Split(re int rt, re int v, re int &x, re int &y) {//带&方便修改
        if (!rt) x = y = 0;
        else {
            if (val[rt] <= v) {
                x = rt;//分给右子树
                Split(ch[rt][1], v, ch[rt][1], y);
            } else {
                y = rt; //分给左子树
                Split(ch[rt][0], v, x, ch[rt][0]);
            }
            PushUp(rt);//上传
        }
    }

插入节点

我们先把树分为 $x,y$ 两部分,然后把新的节点看做是一棵树,先与 $x$ 合并,合并完之后将合并的整体与 $y$ 合并。

inline void Insert(re int v) {
        re int x, y;
        Split(root, v, x, y);
        root = Merge(Merge(x, NewNode(v)), y);
    }

删除节点

首先我们把树分为 $x$ 和 $z$ 两部分,设我们删除节点的权值为 $a$,再把 $x$ 分为 $x$ 和 $y$ 两部分,使得 $x$ 中节点的权值全部小于 $a$,$y$ 中的全部大于 $a$。这就相当于我们传进的参数 $v = a – 1$。 而且呢,权值为 $a$ 的节点正好是 $y$ 树的根。 然后我们可以无视 $y$ 的根节点,直接把 $y$ 的左右孩子合并起来,这样就成功的删除了根节点,最后再把 $x,y,z$ 合并起来就好。结合下面丑图理解:

《平衡树三讲——ylxmf2005的OI教程》

 inline void Delete(re int v) {
      re int x, y, z;
      Split(root, v, x, z);
      Split(x, v - 1, x, y);
      y = Merge(ch[y][0], ch[y][1]);
      root = Merge(Merge(x, y), z);
}

求一个数的排名

考虑二叉查找树的性质:左儿子的值比父亲的小,右儿子的值比父亲大。那么,一个数的排名就是所有比它小的数加上他自己。简单吧?

inline int Lvl(re int v) {
        re int x, y, res;
        Split(root, v - 1, x, y);
        res = siz[x] + 1;
        root = Merge(x, y); //分裂后别忘合并
        return res;
    }

求排名为任意值的数

从根节点出发。根据二叉查找树的性质,如果当前点的值比所在点的值大,那么向右子树走,否则向左子树走。如果排名正好相等就返回值,while 循环就可以解决。可是真的那么简单吗?不,我们向右子树走的时候,左子树会有许多比它权值小的节点,所以我们要减去它左子树的大小。向左子树走的话直接走就可以了。

inline int Kth(re int rt, re int v) {
        while (1) {
            if (v <= siz[ch[rt][0]])
                rt = ch[rt][0];
            else if (v == siz[ch[rt][0]] + 1)
                return val[rt];
            else {
                v -= siz[ch[rt][0]] + 1;
                rt = ch[rt][1];
            }
        }
    }

求一个数的前驱

因为要小于 $a$ ,那么我们按照 $a-1$ 的权值分裂成 $x$ 和 $y$ ,$x$ 中最大的一定是$\leq a – 1$的,所以我们直接输出 $x$ 中最大的数即可。

inline int Pre(re int v) {
        re int x, y, res;
        Split(root, v - 1, x, y);
        res = Kth(x, siz[x]); 
        root = Merge(x, y);
        return res;
    }

求一个数的后继

与求前驱相似,我们只需修改找 $\ge a$ 的最小的数就可以了。

inline int Suf(re int v) {
        re int x, y, res;
        Split(root, v, x, y);
        res = Kth(y, 1);
        root = Merge(x, y);
        return res;
    }

完整模板

#include <bits/stdc++.h>
#define N 100005
#define re register
#define inline inline
using namespace std;
int n;
struct FHQTreap {
    int ch[N][2], val[N], key[N], siz[N], root, cnt;
    inline void PushUp(re int rt) {
        siz[rt] = siz[ch[rt][0]] + siz[ch[rt][1]] + 1;
    }
    inline int NewNode(re int v) {
        siz[++cnt] = 1; val[cnt] = v; key[cnt] = rand();
        return cnt;
    }
    int Merge(re int x, re int y) {
        if (!x || !y) return x + y;
        if (key[x] < key[y]) {
            ch[x][1] = Merge(ch[x][1], y);
            PushUp(x); return x;
        } else {
            ch[y][0] = Merge(x, ch[y][0]);
            PushUp(y); return y;
        }
    }
    void Split(re int rt, re int v, re int &x, re int &y) {
        if (!rt) x = y = 0;
        else {
            if (val[rt] <= v) {
                x = rt;
                Split(ch[rt][1], v, ch[rt][1], y);
            } else {
                y = rt;
                Split(ch[rt][0], v, x, ch[rt][0]);
            }
            PushUp(rt);
        }
    }
    inline void Insert(re int v) {
        re int x, y;
        Split(root, v, x, y);
        root = Merge(Merge(x, NewNode(v)), y);
    }
    inline void Delete(re int v) {
        re int x, y, z;
        Split(root, v, x, z);
        Split(x, v - 1, x, y);
        y = Merge(ch[y][0], ch[y][1]);
        root = Merge(Merge(x, y), z);
    }
    inline int Lvl(re int v) {
        re int x, y, res;
        Split(root, v - 1, x, y);
        res = siz[x] + 1;
        root = Merge(x, y);
        return res;
    }
    inline int Kth(re int rt, re int v) {
        while (1) {
            if (v <= siz[ch[rt][0]])
                rt = ch[rt][0];
            else if (v == siz[ch[rt][0]] + 1)
                return val[rt];
            else {
                v -= siz[ch[rt][0]] + 1;
                rt = ch[rt][1];
            }
        }
    }
    inline int Pre(re int v) {
        re int x, y, res;
        Split(root, v - 1, x, y);
        res = Kth(x, siz[x]);
        root = Merge(x, y);
        return res;
    }
    inline int Suf(re int v) {
        re int x, y, res;
        Split(root, v, x, y);
        res = Kth(y, 1);
        root = Merge(x, y);
        return res;
    }
} T;
int main() {
    scanf("%d", &n);
    for (re int i = 1; i <= n; i++) {
        re int opt, x;
        scanf("%d %d", &opt, &x);
        if (opt == 1) T.Insert(x);
        else if (opt == 2) T.Delete(x);
        else if (opt == 3) printf("%d\n", T.Lvl(x));
        else if (opt == 4) printf("%d\n", T.Kth(T.root, x));
        else if (opt == 5)  printf("%d\n", T.Pre(x));
        else if (opt == 6) printf("%d\n", T.Suf(x));
    }
    return 0;
}

其实用 vector 也可以过这道题,不过也就这一道题而已,并且效率很低。

#include <bits/stdc++.h>
#define L lower_bound(A.begin(),A.end(),x)
#define R upper_bound(A.begin(),A.end(),x)
using namespace std;
int main()
{
    vector<int> A;
    int T;
    cin>>T;
    while(T--)
    {
        int opt,x;
        cin>>opt>>x;
        switch(opt)
        {
            case 1:A.insert(L,x);break;
            case 2:A.erase(L);break;
            case 3:cout<<(L-A.begin())+1<<endl;break;
            case 4:cout<<A[x-1]<<endl;break;
            case 5:cout<<*(--L)<<endl;break;
            case 6:cout<<*R<<endl;break;
        }
    }
    return 0;
}

文艺平衡树

虽然洛谷板子备注是 Splay,但是我们仍然可以用 FHQTreap 简单完美的解决这个问题。

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间(没了)。注意:我们维护的序列是一个排列

这是一个区间问题,我们如何解决这道题呢?我们开始安利一下用大小分的方法,设给定的大小为 $v$,那么我们把数分成 $v$ 与 $size_{rt} – x$。那么分的策略就是:先找左子树,左子树多了分给右子树,不够去和右子树要。

void Split(reg int rt, reg int pos, reg int &x, reg int &y) {
        if (!rt) x = y = 0;
        else {
            PushDown(rt);
            if (pos <= siz[ch[rt][0]]) {
                y = rt;
                Split(ch[rt][0], pos, x, ch[rt][0]);
            } else {
                x = rt;
                Split(ch[rt][1], pos - siz[ch[rt][0]] - 1, ch[rt][1], y);
            }
            PushUp(rt);
        }
    }

细心的小朋友发现了上面有个很熟悉的东东——pushdown,这就是我们熟悉的懒标记,因为这道题直接更新所有的儿子会超时,所以要用懒标记,这个标记还是很简单的,我们只需要用一个数,这个数总为 $0$ 或 $1$,用来表示是否需要反转。代码很简单,我就不贴了。

下面是重头戏:翻转函数 $rev$ 了。我们将树的 $l – 1$ 部分分给 $x$,那么 $y$ 表示的区间为 $[y,n]$。再将 $y$ 分裂出一个 $z$,长度为 $r – l + 1$。最后输出的话,因为平衡树的中序遍历就可以还原序列,所以中序遍历输出即可。下面直接贴全部代码:

#include <bits/stdc++.h>
#define MAXN 100005
#define reg register
#define inl inline
using namespace std;
int n, m;
struct FHQTreap {
    int ch[MAXN][2], val[MAXN], pri[MAXN], siz[MAXN], rev[MAXN], root, cnt;
    inl void PushUp(reg int rt) {
        siz[rt] = siz[ch[rt][0]] + siz[ch[rt][1]] + 1;
    }
    inl void PushDown(reg int rt) {
        if (rev[rt]) {
            swap(ch[rt][0], ch[rt][1]);
            if (ch[rt][0]) rev[ch[rt][0]] ^= 1;
            if (ch[rt][1]) rev[ch[rt][1]] ^= 1;
            rev[rt] = 0;
        }
    }
    inl int NewNode(reg int v) {
        siz[++cnt] = 1;
        val[cnt] = v;
        pri[cnt] = rand();
        return cnt;
    }
    int Merge(reg int x, reg int y) {
        if (!x || !y) return x + y;
        if (pri[x] < pri[y]) {
            if (rev[x]) PushDown(x);
            ch[x][1] = Merge(ch[x][1], y);
            PushUp(x);
            return x;
        } else {
            if (rev[y]) PushDown(y);
            ch[y][0] = Merge(x, ch[y][0]);
            PushUp(y);
            return y;
        }
    }
    void Split(reg int rt, reg int pos, reg int &x, reg int &y) {
        if (!rt) x = y = 0;
        else {
            PushDown(rt);
            if (pos <= siz[ch[rt][0]]) {
                y = rt;
                Split(ch[rt][0], pos, x, ch[rt][0]);
            } else {
                x = rt;
                Split(ch[rt][1], pos - siz[ch[rt][0]] - 1, ch[rt][1], y);
            }
            PushUp(rt);
        }
    }
    inl void Rev(reg int l, reg int r) {
        reg int x, y, z;
        Split(root, l - 1, x, y);
        Split(y, r - l + 1, y, z);
        rev[y] ^= 1;
        root = Merge(x, Merge(y, z));
    }
    void Print(reg int rt) {
        if (!rt) return;
        if (rev[rt]) PushDown(rt);
        Print(ch[rt][0]);
        printf("%d ", val[rt]);
        Print(ch[rt][1]);
    }
} T;
int main() {
    scanf("%d %d", &n, &m);
    for (reg int i = 1; i <= n; i++) T.root = T.Merge(T.root, T.NewNode(i));
    for (reg int i = 1; i <= m; i++) {
        reg int x, y;
        scanf("%d %d", &x, &y);
        T.Rev(x, y);
    }
    T.Print(T.root);
    return 0;
}

可持久化文艺平衡树

您需要写一种数据结构,来维护一个序列,其中需要提供以下操作(对于各个以往的历史版本):

  1. 在第 $p$ 个数后插入数 $x$ 。
  2. 删除第 $p$ 个数。
  3. 翻转区间 $[l,r]$,例如原序列是 ${5,4,3,2,1}{5,4,3,2,1}$,翻转区间 $[2,4]$ 后,结果是 ${5,2,3,4,1}$。
  4. 查询区间 $[l,r]$ 中所有数的和。

和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本(操作 $4$ 即保持原版本无变化),新版本即编号为此次操作的序号。

本题强制在线。

根据可持久化线段树的思想,我们在每次合并与分裂的时候,需要新建一个节点修改,而不是在原来节点上修改。其他的和文艺平衡树差不多。这里介绍一个卡空间的小技巧:每次删除节点的时候,用一个队列记录这个点所占用的空间被 “释放” 了,之后复制节点复制再这个位置上就可以了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct FHQTreap {
    int son[2], val, tot, rev, key;
    ll sum;
} t[200005 << 6];
queue <int> q;
int n, m, tot, root[500005];
int NewNode(int val) {
    int x;
    if (!q.empty()) {
        x = q.front();
        q.pop();
    } else x = ++tot;
    t[x].val = t[x].sum = val;
    t[x].tot = 1;
    t[x].key = rand();
    t[x].son[0] = t[x].son[1] = t[x].rev = 0;
    return x;
}
int Clone(int y) {
    int x;
    if (!q.empty()) {
        x = q.front();
        q.pop();
    } else x = ++tot;
    t[x] = t[y];
    return x;
}
void Update(int x) {
    t[x].tot = t[t[x].son[0]].tot + t[t[x].son[1]].tot + 1;
    t[x].sum = t[t[x].son[0]].sum + t[t[x].son[1]].sum + t[x].val;
}
void PushDown(int x) {
    if (t[x].rev) {
        swap(t[x].son[0], t[x].son[1]);
        if (t[x].son[0]) {
            t[x].son[0] = Clone(t[x].son[0]);
            t[t[x].son[0]].rev ^= 1;
        }
        if (t[x].son[1]) {
            t[x].son[1] = Clone(t[x].son[1]);
            t[t[x].son[1]].rev ^= 1;
        }
        t[x].rev = 0;
    }
}
int Merge(int x, int y) {
    if (!x || !y) return x + y;
    if (t[x].key < t[y].key) {
        PushDown(y);
        t[y].son[0] = Merge(x, t[y].son[0]);
        Update(y);
        return y;
    } else {
        PushDown(x);
        t[x].son[1] = Merge(t[x].son[1], y);
        Update(x);
        return x;
    }
}
void Split(int rt, int pos, int &x, int &y) {
    if (!rt)
        x = y = 0;
    else {
        PushDown(rt);
        if (pos <= t[t[rt].son[0]].tot) {
            y = Clone(rt);
            Split(t[y].son[0], pos, x, t[y].son[0]);
            Update(y);
        } else {
            x = Clone(rt);
            Split(t[x].son[1], pos - t[t[rt].son[0]].tot - 1, t[x].son[1], y);
            Update(x);
        }
    }
}
void Insert(int &rt, int pos, int val) {
    int x, y;
    Split(rt, pos, x, y);
    rt = Merge(Merge(x, NewNode(val)), y);
}
void Delete(int &rt, int pos) {
    int x, y, z;
    Split(rt, pos, x, z);
    Split(x, pos - 1, x, y);
    q.push(y);
    rt = Merge(x, z);
}
void Reverse(int &rt, int l, int r) {
    int x, y, z;
    Split(rt, r, x, z);
    Split(x, l - 1, x, y);
    t[y].rev ^= 1;
    rt = Merge(Merge(x, y), z);
}
ll Query(int &rt, int l, int r) {
    int x, y, z;
    Split(rt, r, x, z);
    Split(x, l - 1, x, y);
    ll res = t[y].sum;
    rt = Merge(Merge(x, y), z);
    return res;
}
int main() {
    ll lat = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int v, opt;
        scanf("%d %d", &v, &opt);
        root[i] = root[v];
        if (opt == 1) {
            int pos, x;
            scanf("%d %d", &pos, &x);
            pos ^= lat; x ^= lat;
            Insert(root[i], pos, x);
        } else if (opt == 2) {
            int pos;
            scanf("%d", &pos);
            pos ^= lat;
            Delete(root[i], pos);
        } else if (opt == 3) {
            int x, y;
            scanf("%d %d", &x, &y);
            x ^= lat; y ^= lat;
            Reverse(root[i], x, y);
        } else {
            int x, y;
            scanf("%d %d", &x, &y);
            x ^= lat; y ^= lat;
            lat = Query(root[i], x, y);
            printf("%lld\n", lat);
        }
    }
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据