[C++] pb_ds库中的平衡树

简介

pb_ds库中的tree是平衡树,有rb_tree、splay_tree、ov_tree三种类型。

使用方法

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
__gnu_pbds ::tree<long long, __gnu_pbds ::null_type, std::less_equal<long long>, __gnu_pbds ::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> tree;
/*
template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>, typename Tag = rb_tree_tag, template< typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_ > class Node_Update = pb_ds::null_tree_node_update, typename Allocator = std::allocator<char>>
class pb_ds::tree< Key, Mapped, Cmp_Fn, Tag, Node_Update, Allocator >
Key: 键的类型
Mapped: 映射类型
Cmp_Fn: 对键比较时用的仿函数,默认为std::less<Key>
Tag: 用来指定使用数据结构的标签,默认为__gnu_pbds::rb_tree_tag
Node_Update: 更新结点的方式,默认为__gnu_pbds ::null_node_update
Allocator: 空间配置器,默认为std::allocator<char>
 */
int main() {
    int x = 1;
    tree.insert(x); // 插入一个结点,如果Cmp_Fn为std::less_equal<Key>,那么就可以插入重复节点
    tree.upper_bound(x); // 查找第一个大于该值(std::less_equal<Key>则为大于等于)的结点,返回的是迭代器
    tree.lower_bound(x); // 查找第一个大于等于该值(std::less_equal<Key>则为大于)的结点,返回的是迭代器
    tree.erase(tree.lower_bound(x)); // 删除一个结点,传入参数为迭代器
    tree.order_of_key(x); // 查询一个结点的排名,返回的是排名(从0开始)
    tree.find_by_order(x); // 由排名(从0开始)查找结点,返回的是迭代器
    return 0;
}

洛谷P3369 【模板】普通平衡树 / BZOJ3224 Tyvj 1728 普通平衡树

此题插入操作会出现重复的数,如果用std::less<Key>将无法插入重复的数。对此,我们可以用一些玄学方法来避免键冲突,比如左移20位+编号使用std::pair作为键。然而,使用std::less_equal<Key>就可以插入重复的数,无需再处理键冲突了。

代码:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
__gnu_pbds ::tree<long long, __gnu_pbds ::null_type, std::less_equal<long long>,
        __gnu_pbds ::rb_tree_tag, __gnu_pbds ::tree_order_statistics_node_update> tree;
int n, opt, x;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    while (n--) {
        std::cin >> opt >> x;
        switch (opt) {
        case 1:
            tree.insert(x);
            break;
        case 2:
            tree.erase(tree.upper_bound(x));
            break;
        case 3:
            std::cout << tree.order_of_key(x) + 1 << std::endl;
            break;
        case 4:
            std::cout << *tree.find_by_order(x - 1) << std::endl;
            break;
        case 5:
            std::cout << *--tree.upper_bound(x) << std::endl;
            break;
        case 6:
            std::cout << *tree.lower_bound(x) << std::endl;
            break;
        }
    }
    return 0;
}

参考资料

https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.2/classpb__ds_1_1tree.html

https://www.luogu.org/blog/Chanis/gnu-pbds

https://blog.csdn.net/simpsonk/article/details/79390625

https://www.luogu.org/recordnew/show/14721934

About the Author: 心水湛清

发表评论

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