- C24zhuchengyu's blog
C++11自带平衡树!
- @ 2025-10-31 13:46:11
头文件:
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;//命名空间
定义方式:
// 不可重集合定义
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
// 可重集合定义(使用pair区分相同元素)
typedef tree<pair<int, int>, null_type, less<pair<int, int>>,
rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
插入操作:
ordered_set s;
s.insert(1);
s.insert(3);
s.insert(5);
删除操作:
s.erase(s.lower_bound(3)); // 删除第一个等于3的元素
查询排名(严格小于):
int rank = s.order_of_key(4); // 返回小于4的元素个数
按排名查询:
auto it = s.find_by_order(1); // 获取第2小的元素
int value = *it;