[数据结构与算法]平衡树（模板）

平衡树の模板

您需要写一种数据结构，来维护一些数，其中需要提供以下操作：

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

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, INF = 1e8;
int n;
struct Node{
    int l, r;
    int key, val;
    int cnt, sz;
}tr[N];
int root, idx;
void pushup(int p)
{
    tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + tr[p].cnt;
}
int get_node(int key)
{
    tr[++ idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].sz = 1;
    return idx;
}
void zig(int &p) // 右旋
{
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    pushup(tr[p].r), pushup(p);
}
void zag(int &p) // 左旋
{
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    pushup(tr[p].l),pushup(p);
}
void build()
{
    get_node(-INF), get_node(INF);// 两个哨兵，防止越界问题
    root = 1; tr[1].r = 2;
    pushup(root);
    if(tr[1].val < tr[2].val) zag(root);
}
// 插入操作
void insert(int &p, int key)
{
    if(!p) p = get_node(key);
    else if(tr[p].key == key) tr[p].cnt ++;
    else if(tr[p].key > key) 
    {
        insert(tr[p].l, key);
        if(tr[tr[p].l].val > tr[p].val) zig(p);
    }
    else 
    {
        insert(tr[p].r, key);
        if(tr[tr[p].r].val > tr[p].val) zag(p);
    }
    pushup(p);
}
// 删除操作
void del(int &p, int key)
{
    if(!p) return ;
    if(tr[p].key == key)
    {
        if(tr[p].cnt > 1) tr[p].cnt --;
        else if(tr[p].l || tr[p].r)
        {
            if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) 
            {
                zig(p);
                del(tr[p].r, key);
            }
            else {
                zag(p);
                del(tr[p].l, key);
            }
        }
        else p = 0;
    }
    else if(tr[p].key > key) del(tr[p].l, key);
    else del(tr[p].r, key);
    
    pushup(p);
}

int get_rank_by_key(int p, int key)    // 通过数值找排名
{
    if (!p) return 0;
    if (tr[p].key == key) return tr[tr[p].l].sz + 1;
    if (tr[p].key > key) return get_rank_by_key(tr[p].l, key);
    return tr[tr[p].l].sz + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}

int get_key_by_rank(int p, int rank)   // 通过排名找数值
{
    if (!p) return INF; 
    if (tr[tr[p].l].sz >= rank) return get_key_by_rank(tr[p].l, rank);
    if (tr[tr[p].l].sz + tr[p].cnt >= rank) return tr[p].key;
    return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].sz - tr[p].cnt);
}

int get_prev(int p, int key) // 获得小于key的最大值
{
    if(!p) return -INF;
    if(tr[p].key >= key ) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key) //获得大于key的最小值
{
    if(!p) return INF;
    if(tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}
int main()
{
    build();
    scanf("%d", &n);
    while(n -- )
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if(opt == 1) insert(root, x);
        else if(opt == 2) del(root, x);
        else if(opt == 3) printf("%d\n", get_rank_by_key(root, x) - 1);
        else if(opt == 4) printf("%d\n", get_key_by_rank(root, x + 1));
        else if(opt == 5) printf("%d\n", get_prev(root, x));
        else printf("%d\n", get_next(root, x));
    }
}