pb_ds之红黑树

STL

在GNU C++的pb_ds库中，有可以调用的红黑数模板，可用于实现set的全部功能，并且还可以快速的求数的排名，和第k小等。

需要包含的头文件和命名空间

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

定义一颗红黑树

tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> t;

第一个参数代表key的类型
第二个参数表示value的类型。这里不需要映射值，也就填null_type。在老版本G++中这个需要替换为null_mapped_type（如BZOJ）。
第三个参数表示key的排序方式，从小到大。
第四个参数表示使用哪种数据结构，rb_tree_tag表示红黑树。
第五个参数表示如何更新保存节点信息，填写tree_order_statistics_node_update会额外获得order_of_key()和find_by_order()两个功能。

tree也使用和set类似的迭代器，定义为

tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>::iterator it;

要保证迭代器类型要和定义的树的类型相同。但是为了方便，在条件允许的情况下，可以用auto来自动推断类型。如：

auto it = t.begin();

当然这个迭代器支持++和--操作。
功能简介

1、tree包含set的全部功能，如lower_bound, upper_bound, insert, erase, find, begin, end, rbegin等。
2、查询第k+1小的数，使用find_by_order()函数，返回的为迭代器。

cout << *t.find_by_order(2) << endl;

此时输出的为排名为3的数，注意，查询的是为第k+1小的数。如果传入的k值非法，则会返回end()。
3、查询比x小的数的个数，注意，是比x小的个数，不是x的排名！查询的出的值是排名-1。

cout << t1.order_of_key(2) << endl;

4、合并两个类型相同的tree，t1.join(t2)。t2的内容会全部加入到t1，t2被清空。要保证t1的值全部小于t2或者全部大于t2，否则会抛出异常。
5、不支持多重值，如果需要多重值，可以再开一个unordered_map来记录值出现的次数。将x<<32后加上出现的次数后插入tree。注意此时应该为long long类型。

auto it=t.begin();
it--;
//此时的
it==t.end();
t.end()不是最后一位，是最后一位的下一位

例子：PowerOJ2268
代码

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
int main()
{
    tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> t;
    char s[20];
    while(~scanf("%s", s), s[0] != '-')
    {
        if(s[0] == 'i')
        {
            int x;
            scanf("%d", &x);
            t.insert(x);    //插入x值
        }
        else if(s[0] == 'd')
        {
            int x;
            scanf("%d", &x);
            auto it = t.find(x);    //查询x值
            if(it != t.end()) t.erase(x);   //删除x值，也可以删除迭代器
            else printf("Input Error\n");
        }
        else if(s[0] == 'p')
        {
            if(s[2] == 'e')
            {
                int x;
                scanf("%d", &x);
                auto it = t.find(x);
                if(it != t.end())
                {
                    it--;   //迭代器--，求前驱
                    if(it == t.end()) printf("%d is the minimum\n", x);
                    else printf("The predecessor of %d is %d\n", x, *it);
                }
                else printf("Input Error\n");
            }
            else
            {
                for(auto &i : t) printf("%d,", i);  //遍历整个树，用迭代器遍历从beign到end也可以
                printf("end of print\n");
            }
        }
        else if(s[0] == 's')
        {
            int x;
            scanf("%d", &x);
            auto it = t.find(x);
            if(it != t.end())
            {
                it++;  //迭代器++，求前驱
                if(it == t.end()) printf("%d is the maximum\n", x);
                else printf("The successor of %d is %d\n", x, *it);
            }
            else printf("Input Error\n");
        }
        else if(s[0] == 'K')
        {
            int x;
            scanf("%d", &x);
            if(x > t.size() || x <= 0) printf("Input Error\n");
            else printf("The %d_th element is %d\n", x, *t.find_by_order(x - 1));   //查第k小，注意-1
        }
        else if(s[0] == 'r')
        {
            int x;
            scanf("%d", &x);
            auto it = t.find(x);
            if(it != t.end()) printf("The rank of %d is %d_th\n", x, t.order_of_key(x) + 1);    //查排名，注意+1
            else printf("Input Error\n");
        }
        else
        {
            printf("end of this test\n");
            t.clear();  //清空
        }
    }
    return 0;
}