题解 | 普通平衡树

题干分析

题设要求我们动态维护一个有序数据结构，并进行若干次6种操作。

算法思路

本题有两种解决思路，一种是放弃使用树状结构，直接使用STL库提供的二分查找算法与vector容器实现。

另一种思路是维护树状的二叉查找树进行实现，同时为了提高查找效率，我们得防止我们构建的树过于不平衡，也就是说我们需要动态维护一个平衡二叉搜索树。这里个人做法是实现一颗替罪羊树，设定一个不平衡率，只要子树达到该不平衡率我们就直接重建一颗相对平衡的子树。同时针对删除，我们采取懒删除方式标记删除节点，当树发生重建时再真正删除。

实现代码

• 使用STL库+vector容器实现：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    vector<int> v;
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        int op, x;
        cin >> op >> x;
        switch (op) {
            case 1:
                v.insert(ranges::lower_bound(v, x), x);
                break;
            case 2:
                v.erase(ranges::lower_bound(v, x));
                break;
            case 3:
                cout << ranges::lower_bound(v, x) - v.begin() + 1 << endl;
                break;
            case 4:
                cout << v[x - 1] << endl;
                break;
            case 5:
                cout << v[ranges::lower_bound(v, x) - v.begin() - 1] << endl;
                break;
            case 6:
                cout << v[ranges::upper_bound(v, x) - v.begin()] << endl;
                break;
            default: ;
        }
    }

    return 0;
}//*/

• 维护替罪羊树的实现：

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

// 替罪羊树
class ScapegoatTree {
    const int N; // 最高节点数
    const double alpha; // 不平衡率

    struct Node {
        int leftSon, rightSon; // 记录下标，为0表示空
        int val;
        int total; // 当前子树占用空间数量，包括懒删除节点
        int size; // 子树实际存在节点数
        bool del; // 删除标记
    };

    vector<Node> t; // 扁平存储
    vector<int> order; // 记录子树销毁后的节点大小顺序(下标)
    int cnt = 0; // 销毁子树的节点数
    stack<int> treeStack; // 使用栈回收和分配可用节点（下标）
    int root = 0; // 根节点(下标)

    // 中序遍历摧毁子树
    void inOrder(const int cur) {
        if (cur) {
            inOrder(t[cur].leftSon);
            if (t[cur].del) order[++cnt] = cur;
            else treeStack.push(cur);
            inOrder(t[cur].rightSon);
        }
    }

    // 重置节点参数
    void initNode(const int idx) {
        t[idx].leftSon = t[idx].rightSon = 0;
        t[idx].size = t[idx].total = 1;
        t[idx].del = true;
    }

    // 更新节点大小数据
    void update(const int idx) {
        t[idx].size = t[t[idx].leftSon].size + t[t[idx].rightSon].size + 1;
        t[idx].total = t[t[idx].leftSon].total + t[t[idx].rightSon].total + 1;
    }

    // 重建
    void build(int left, int right, int &cur) {
        int mid = (left + right) >> 1;
        cur = order[mid];
        // 叶子节点
        if (left == right) {
            initNode(cur);
            return;
        }
        // 重构左子树
        if (left < mid) build(left, mid - 1, t[cur].leftSon);
        if (left == mid) t[cur].leftSon = 0; // 左子树为空
        // 重构右子树
        build(mid + 1, right, t[cur].rightSon);
        // 更新大小
        update(cur);
    }

    // 启动重建
    void rebuild(int &tar) {
        cnt = 0;
        inOrder(tar);
        if (cnt) build(1, cnt, tar);
        else tar = 0;
    }

    // 判断是否平衡
    [[nodiscard]] bool isUnbalance(const int tar) const {
        return static_cast<double>(t[tar].size) * alpha <=
               static_cast<double>(max(t[t[tar].leftSon].size, t[t[tar].rightSon].size));
    }

    // 插入x
    void insert(int &u, const int x) {
        if (!u) {
            // u为空节点
            u = treeStack.top();
            treeStack.pop();
            t[u].val = x;
            initNode(u);
            return;
        }
        t[u].size++;
        t[u].total++;
        if (t[u].val >= x) insert(t[u].leftSon, x); // 插左树
        else insert(t[u].rightSon, x); // 插右树
        if (isUnbalance(u)) rebuild(u); // 不平衡，重建子树
    }

    // x的排名
    int rank(const int u, const int x) {
        if (u == 0) return 0;
        if (x > t[u].val) {
            const int tmp = t[t[u].leftSon].size + (t[u].del ? 1 : 0);
            return tmp + rank(t[u].rightSon, x);
        }
        return rank(t[u].leftSon, x);
    }

    // 删除排名k的数
    void delK(const int &u, const int k) {
        t[u].size--;
        if (t[u].del && t[t[u].leftSon].size + 1 == k) {
            t[u].del = false;
            return;
        }
        // 左子树上
        if (t[t[u].leftSon].size + (t[u].del ? 1 : 0) >= k) delK(t[u].leftSon, k);
            // 右子树上
        else delK(t[u].rightSon, k - t[t[u].leftSon].size - (t[u].del ? 1 : 0));
    }

public:
    explicit ScapegoatTree(const int N_ = 1e6 + 10, const double alpha_ = 0.75) : N(N_), alpha(alpha_) {
        t.resize(N);
        order.resize(N);
        // 记录所有可用的t
        for (int i = N - 1; i >= 1; --i) treeStack.push(i);
    }

    // 对外插入接口
    void Insert(const int x) { insert(root, x); }

    // 对外排名接口
    int Rank(const int x) { return rank(root, x); }

    // 排名第k大的数
    [[nodiscard]] int kth(int k) const {
        int u = root;
        while (u) {
            if (t[u].del && t[t[u].leftSon].size + 1 == k) return t[u].val;
            if (t[t[u].leftSon].size >= k) u = t[u].leftSon;
            else {
                k -= t[t[u].leftSon].size + (t[u].del ? 1 : 0);
                u = t[u].rightSon;
            }
        }
        return t[u].val;
    }

    // 对外删除第k个元素接口
    void DelK(const int k) { delK(root, k); }

    // 删除值为x的数
    void del(const int x) {
        delK(root, rank(root, x) + 1);
        // 已删除节点过多，重构整个树
        if (t[root].total * alpha >= t[root].size) rebuild(root);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ScapegoatTree tree;
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int op, x;
        cin >> op >> x;
        switch (op) {
            case 1:
                tree.Insert(x);
                break;
            case 2:
                tree.del(x);
                break;
            case 3:
                cout << tree.Rank(x) + 1 << endl;
                break;
            case 4:
                cout << tree.kth(x) << endl;
                break;
            case 5:
                cout << tree.kth(tree.Rank(x)) << endl;
                break;
            case 6:
                cout << tree.kth(tree.Rank(x + 1) + 1) << endl;
                break;
            default: ;
        }
    }

    return 0;
}

复杂度分析

• 时间复杂度：

1类操作针对vector容器实现为，平衡树实现均摊为

2类操作针对vector容器实现也为,平衡树实现均摊为

3类操作二者均为

4类操作针对vector容器实现为,平衡树实现均摊为

5类操作二者均为

6类操作二者均为

• 空间复杂度：二者均为