title: “平衡树”
date: 2024-06-03 10:42:02
updated: 2024-06-05 07:32:22
tag: [“notion”, “Algorithm”, “树与图”]
categories: “Algorithm”
mathjax: true
comments: true
description: ‘

• 平衡树

平衡树

splay

伸展树特点就是每次操作完一个节点，将其旋转至根，保证BST性质的同时保持平衡不至于退化成链。对于一条长链，底端的节点旋转至顶会让这条链被压缩。

旋转rotate操作，分为左旋与右旋

{% asset_img ‘Untitled.png’ %}

伸展splay操作是旋转的组合，将某子树内节点x变为根节点。

• 当x已经成为根的子节点时，做单次旋转
• 否则存在x的父节点y，爷节点z
  • x-y-z处于一条“直链”，则先旋转y再旋转x
  • x-y-z处于一条“折链”，则先旋转x再旋转x

{% asset_img ‘Untitled 1.png’ %}

{% asset_img ‘Untitled.gif’ %}

P3369 【模板】普通平衡树

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

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

基于伸展操作，可以实现以下操作

• 插入x。二叉查找树的性质可以找到x，让节点计数值自增；否则若x不存在，则会增加一个叶子x。然后为了保证不退化成链，让x旋转至根。
• 删除x。让x前驱旋转至根，再让x后继旋转至根的右儿子，此时x必是叶子。减少x节点计数值，若为0则直接删除节点x。
• 找到x的排名。x旋转至根，则左子树的大小+1就是x的排名。（注意具体实现时，会添加正负无穷哨兵避免边界特判的复杂实现）
• 找到排名为r的值。基于各子树大小与二叉查找树的性质实现。
• 找到x的前驱/后继。让x旋转至根，找左/右子树中的最大/小值即为前驱/后继。

所有操作均摊$O(logn)$

// https://www.luogu.com.cn/problem/P3369
#include <iostream>
using namespace std;

#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
const int N = 1100010, INF = (1 << 30) + 1;
struct node {
    int s[2];  // 左右儿子
    int p;     // 父亲
    int v;     // 节点权值
    int cnt;   // 权值出现次数
    int siz;   // 子树大小
    void init(int p1, int v1) {
        p = p1, v = v1;
        cnt = siz = 1;
    }
} tr[N];

int root;  // 根节点编号
int idx;   // 节点个数

void pushup(int x) {
    tr[x].siz = tr[ls(x)].siz + tr[rs(x)].siz + tr[x].cnt;
}

// 左/右旋 6个指针的断开重连
void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1];
    tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y;
    tr[y].p = x;
    pushup(y), pushup(x);
}

// 将x不断旋转至k的儿子，k为0则x变为根
void splay(int x, int k) {
    while (tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)  // 折转底，直转中
            (ls(y) == x) ^ (ls(z) == y) ? rotate(x) : rotate(y);
        rotate(x);
    }
    if (!k)
        root = x;
}

// 先二分查找，找到v则自增，否则添加新节点v（添加的位置必为叶子），并将v旋转至根
void insert(int v) {  // 插入
    int x = root, p = 0;
    while (x && tr[x].v != v)
        p = x, x = tr[x].s[v > tr[x].v];
    if (x)
        tr[x].cnt++;
    else {
        x = ++idx;
        if (p)
            tr[p].s[v > tr[p].v] = x;
        tr[x].init(p, v);
    }
    splay(x, 0);
}

// 二分找到值为v的节点，然后旋转至根。
// v不存在，返回 小于v的最大值 或 大于v的最小值 节点
void find(int v) {  // 找到v并转到根
    int x = root;
    while (tr[x].s[v > tr[x].v] && v != tr[x].v)
        x = tr[x].s[v > tr[x].v];
    splay(x, 0);
}

// find(v)，根节点值小于v，则根节点就是v的前驱
// 否则根左子树的最大值为前驱
int getpre(int v) {  // 前驱
    find(v);
    int x = root;
    if (tr[x].v < v)
        return x;
    x = ls(x);
    while (rs(x))
        x = rs(x);
    splay(x, 0);
    return x;
}

// find(v)，根节点值大于v，则根节点就是v的后继
// 否则根右子树的最小值为后继
int getsuc(int v) {  // 后继
    find(v);
    int x = root;
    if (tr[x].v > v)
        return x;
    x = rs(x);
    while (ls(x))
        x = ls(x);
    splay(x, 0);
    return x;
}

// 找到v的前驱和后继，让前驱成为根，后继成为根的右儿子
// 由于v的前驱后继唯一，所以此时v必为叶子节点。
void del(int v) {  // 删除
    int pre = getpre(v);
    int suc = getsuc(v);
    splay(pre, 0), splay(suc, pre);
    int del = tr[suc].s[0];
    if (tr[del].cnt > 1)
        tr[del].cnt--, splay(del, 0);
    else
        tr[suc].s[0] = 0, splay(suc, 0);
}

// 值为v在树中的排名，其左子树的大小就是排名（负无穷哨兵的存在）
int getrank(int v) {  // 排名
    insert(v);
    int res = tr[tr[root].s[0]].siz;
    del(v);
    return res;
}

// 获取排名为k的值，二分
int getval(int k) {  // 数值
    int x = root;
    while (true) {
        if (k <= tr[ls(x)].siz)  // 其必在左子树
            x = ls(x);
        else if (k <= tr[ls(x)].siz + tr[x].cnt)
            break;
        else
            k -= tr[ls(x)].siz + tr[x].cnt, x = rs(x);
    }
    splay(x, 0);
    return tr[x].v;
}
// 插入哨兵 insert(-INF), insert(INF)
// 插入，删除，查询节点值x排名，查询排名x的节点值，查询节点值x的前驱和后继节点值

int main() {
    insert(-INF);
    insert(INF);  // 哨兵
    int n, op, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &op, &x);
        if (op == 1)
            insert(x);
        else if (op == 2)
            del(x);
        else if (op == 3)
            printf("%d\n", getrank(x));
        else if (op == 4)
            printf("%d\n", getval(x + 1));
        else if (op == 5)
            printf("%d\n", tr[getpre(x)].v);
        else
            printf("%d\n", tr[getsuc(x)].v);
    }
    return 0;
}

P3391 【模板】文艺平衡树

您需要写一种数据结构，来维护一个有序数列。
其中需要提供以下操作：翻转一个区间，例如原有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。
第一行两个正整数 $n,m$，表示序列长度与操作个数。序列中第 $i$ 项初始为 $i$。
接下来 $m$ 行，每行两个正整数 $l,r$，表示翻转的区间。
输出一行 $n$ 个正整数，表示原始序列经过 $m$ 次变换后的结果。

对于已经构成的二叉树，其中序遍历是原有序列，我们对区间的反转实际是对其中一颗子树的反转？实际并不是。与线段树类似一个区间可能覆盖了多颗子树。

但是我们可以利用splay操作将区间[l,r] 内的节点聚集在一颗子树上。具体做法就是找到排名为l-1的节点编号x，找到排名为r+1的节点编号y。通过伸展操作让x为根，y为x的右儿子。这时区间[l,r] 所有节点都在y的左子树上。

我们要反转区间[l,r] 。只需对这颗子树的反转，可以为其打上懒标记。懒标记的作用在于当遍历到含懒标记的节点时交换左右儿子，并传递懒标记。对于打上偶数次懒标记相当于交换偶数次，也就是无需交换。

我们发现本题构造了一颗二叉平衡树，但是却不是二叉搜索树（反转操作后，中序遍历二叉树并不是有序的）。但是找到排名为k的节点编号却可以用二叉搜索实现，其二叉搜索的条件取决于子树的节点数目而不是子节点的值。

我们找到排名为k的节点编号x，然后将x旋转至根，这个过程中时不会遇到懒标记的，因为在找x的过程中所经过的节点都会处理懒标记。所以x旋转至根的这条链上不会遇到懒标记。

最后中序遍历输出，过程中遇到懒标记便处理并下传。

// https://www.luogu.com.cn/problem/P3391
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 100005
#define MOD 998244353
#define INF 0x3f3f3f3f
#define NINF 0xf3f3f3f3
using namespace std;

#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]

struct node {
    int s[2];  // 左右儿子
    int p;     // 父亲
    int v;     // 节点权值
    int siz;   // 子树大小
    int tag;
    void init(int p1, int v1) {
        p = p1, v = v1;
        siz = 1;
        tag = 0;
    }
} tr[N];

int root;  // 根节点编号
int idx;   // 节点个数

void pushup(int x) {
    tr[x].siz = tr[ls(x)].siz + tr[rs(x)].siz + 1;
}

void pushdown(int x) {
    if (tr[x].tag) {
        swap(ls(x), rs(x));
        tr[ls(x)].tag ^= 1;
        tr[rs(x)].tag ^= 1;
        tr[x].tag = 0;
    }
}

// 左/右旋 6个指针的断开重连
void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1];
    tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y;
    tr[y].p = x;
    pushup(y), pushup(x);
}

// 将x不断旋转至k的儿子，k为0则x变为根
void splay(int x, int k) {
    while (tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)  // 折转底，直转中
            (ls(y) == x) ^ (ls(z) == y) ? rotate(x) : rotate(y);
        rotate(x);
    }
    if (!k)
        root = x;
}

// 先二分查找，找到v则自增，否则添加新节点v（添加的位置必为叶子），并将v旋转至根
void insert(int v) {  // 插入
    int x = root, p = 0;
    while (x && tr[x].v != v)
        p = x, x = tr[x].s[v > tr[x].v];
    x = ++idx;
    if (p)
        tr[p].s[v > tr[p].v] = x;
    tr[x].init(p, v);
    splay(x, 0);
}

// 获取排名为k的节点编号
int getid(int k) {
    int x = root;
    while (true) {
        pushdown(x);
        if (k <= tr[ls(x)].siz)  // 其必在左子树
            x = ls(x);
        else if (k == tr[ls(x)].siz + 1)
            break;
        else
            k -= tr[ls(x)].siz + 1, x = rs(x);
    }
    return x;
}

void dfs(int o) {
    if (!o)
        return;
    pushdown(o);
    dfs(ls(o));
    if (tr[o].v != INF && tr[o].v != NINF)
        cout << tr[o].v << " ";
    dfs(rs(o));
}

void sol() {
    insert(NINF);
    insert(INF);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        insert(i);
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        // 将排名为 [l+1, r+1] 聚集到一颗子树上，然后打上懒标记
        int x = getid(l), y = getid(r + 2);
        splay(x, 0);
        splay(y, x);
        tr[ls(y)].tag ^= 1;
    }
    dfs(root);
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

FHQ Treap

无旋Treap每颗子树内，节点权值val满足二叉查找树的性质，节点随机值key满足堆的性质。节点的随机值保证了形成的树不会退化成链较为平衡。

通过分割操作将一颗树分为两颗treap树x和y，x树内节点值均小于等于v，y树内节点值均大于v。

通过合并操作将两颗treap树合为一颗treap树。

{% asset_img ‘Untitled 2.png’ %}

P3369 【模板】普通平衡树

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

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

通过分割与合并可以实现：

• 插入x。直接以x作为分割点分割成两树，然后将x视为一颗树，将三颗树合并即可。
• 删除x。先分割成三颗树a,b,c，a树内节点值均小于x，b树内节点值等于x，c树内节点均大于x。随后让b树两子节点合并成为新的b树。这样相当于删除了b树的根节点，然后让a,b,c三树合并。
• 找到x的排名。分割出节点值均小于x的树a，a的大小+1就是当前x的排名。
• 找到排名为r的值。利用子树大小与BST的性质，二叉查找。
• 找到x的前驱/后继。分割出节点值小/大于x的树a，a中最大/小值为x的前驱/后继

// https://www.luogu.com.cn/problem/P3369
#include <iostream>
using namespace std;

const int N = 100005;
struct node {
    int l, r;  // 左右儿子
    int val;   // 树的权值
    int rnd;   // 堆的随机值
    int size;  // 子树大小
} tr[N];
int root, idx;

void newnode(int& x, int v) {
    x = ++idx;
    tr[x].val = v;
    tr[x].rnd = rand();
    tr[x].size = 1;
}

void pushup(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
}

// 从根节点p开始将树分裂成以x为根和y为根的两棵树
// x树内节点值均小于等于v，y树内节点值均大于v
void split(int p, int v, int& x, int& y) {
    if (!p) {
        x = y = 0;
        return;
    }
    if (tr[p].val <= v) {
        x = p;
        split(tr[x].r, v, tr[x].r, y);
        pushup(x);
    } else {
        y = p;
        split(tr[y].l, v, x, tr[y].l);
        pushup(y);
    }
}

// x树和y树合并成新树，返回根节点
int merge(int x, int y) {
    if (!x || !y)
        return x + y;
    if (tr[x].rnd < tr[y].rnd) {
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    } else {
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

// 插入v节点，以v为分割拆分成两个树x和y，将x,v,y三树合并
void insert(int v) {
    int x, y, z;
    split(root, v, x, y);
    newnode(z, v);
    root = merge(merge(x, z), y);
}

// 拆分出三颗树，x树内值小于v，y树内值等于v，z树内值大于v。
// y树左右子树合并成为新的y树，相当于将根删除，删除了一个v节点。
// 合并x, y, z三颗树。
void del(int v) {
    int x, y, z;
    split(root, v, x, z);
    split(x, v - 1, x, y);
    y = merge(tr[y].l, tr[y].r);
    root = merge(merge(x, y), z);
}

// 获取值的排名，以v-1进行分割，得到x树内值都小于等于v-1
// x树大小+1为v值的排名
int getrank(int v) {
    int x, y;
    split(root, v - 1, x, y);
    int ans = tr[x].size + 1;
    root = merge(x, y);
    return ans;
}

// 获取排名为v的值，二分
int getval(int root, int v) {
    if (v == tr[tr[root].l].size + 1)
        return tr[root].val;
    else if (v <= tr[tr[root].l].size)
        return getval(tr[root].l, v);
    else
        return getval(tr[root].r, v - tr[tr[root].l].size - 1);
}

// v值前驱，拆分出x树，x树内值均小于v
// 找到x树内最大值
int getpre(int v) {
    int x, y, s, ans;
    split(root, v - 1, x, y);
    s = tr[x].size;
    ans = getval(x, s);
    root = merge(x, y);
    return ans;
}

// v值前驱，拆分出y树，x树内值均大于v
// 找到y树内最小值
int getnxt(int v) {
    int x, y, ans;
    split(root, v, x, y);
    ans = getval(y, 1);
    root = merge(x, y);
    return ans;
}

int main() {
    int n, op, v;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &op, &v);
        if (op == 1)
            insert(v);
        else if (op == 2)
            del(v);
        else if (op == 3)
            printf("%d\n", getrank(v));
        else if (op == 4)
            printf("%d\n", getval(root, v));
        else if (op == 5)
            printf("%d\n", getpre(v));
        else
            printf("%d\n", getnxt(v));
    }
    return 0;
}

P3391 【模板】文艺平衡树

您需要写一种数据结构，来维护一个有序数列。
其中需要提供以下操作：翻转一个区间，例如原有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。
第一行两个正整数 $n,m$，表示序列长度与操作个数。序列中第 $i$ 项初始为 $i$。
接下来 $m$ 行，每行两个正整数 $l,r$，表示翻转的区间。
输出一行 $n$ 个正整数，表示原始序列经过 $m$ 次变换后的结果。

对于splay可以将利用伸展操作将区间[l,r] 内的节点聚集在一颗子树上。而无旋treap也可以将区间聚集到一颗树上，然后打上懒标记。可以按照排名分裂，先将区间[1,n]分为[1, r], [r+1, n]，然后将[1, r]分为[1, l-1], [l, r] 。然后将[l,r]子树打上懒标记。

合并和分割操作遇到的每个节点都需要处理懒标记。

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 100005
#define MOD 998244353
using namespace std;

struct node {
    int l, r;  // 左右儿子
    int val;   // 树的权值
    int rnd;   // 堆的随机值
    int size;  // 子树大小
    int tag;   // 懒标记
} tr[N];
int root, idx;

void newnode(int& x, int v) {
    x = ++idx;
    tr[x].val = v;
    tr[x].rnd = rand();
    tr[x].size = 1;
    tr[x].tag = 0;
}

void pushup(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
}

void pushdown(int p) {
    if (tr[p].tag) {
        swap(tr[p].l, tr[p].r);
        tr[tr[p].l].tag ^= 1;
        tr[tr[p].r].tag ^= 1;
        tr[p].tag = 0;
    }
}

// 按照排名进行分裂，节点排名小于等于v划分到x，其余划分到y
void split(int p, int v, int& x, int& y) {
    if (!p) {
        x = y = 0;
        return;
    }
    pushdown(p);                 // 向下分裂过程中处理懒标记
    if (tr[tr[p].l].size < v) {  // 当前划分到x
        v -= tr[tr[p].l].size + 1;
        x = p;
        split(tr[x].r, v, tr[x].r, y);
    } else {
        y = p;
        split(tr[y].l, v, x, tr[y].l);
    }
    pushup(p);
}

// x树和y树合并成新树，返回根节点
int merge(int x, int y) {
    if (!x || !y)
        return x + y;
    if (tr[x].rnd < tr[y].rnd) {
        pushdown(x);
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    } else {
        pushdown(y);
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

// 插入v节点，以v为分割拆分成两个树x和y，将x,v,y三树合并
void insert(int v) {
    int x, y, z;
    split(root, v, x, y);
    newnode(z, v);
    root = merge(merge(x, z), y);
}

void dfs(int p) {
    if (!p)
        return;
    pushdown(p);
    dfs(tr[p].l);
    cout << tr[p].val << " ";
    dfs(tr[p].r);
}

void sol() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        insert(i);
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        int a, b, c;
        // 由于按照排名分裂的缘故，分裂有顺序要求
        split(root, r, a, c);   // 先分开[1 r] [r+1, n]
        split(a, l - 1, a, b);  // 再分开[1, l-1] [l, r]
        tr[b].tag ^= 1;
        root = merge(merge(a, b), c);
    }
    dfs(root);
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}