是否存在类似C++ std::set且可快速查询指定范围内元素数量的数据结构

你需要的功能完全可以通过增强型有序集合实现，以下是不同场景下的可选方案：

1. 顺序统计树（Order Statistic Tree, OST）- 最优精确解 #

这是完全匹配你需求的标准数据结构，本质就是在红黑树的每个节点上额外存储该节点对应子树的元素总数，树旋转时同步更新该计数即可，完全保留了普通红黑树的特性：

• 插入、删除、查找单元素时间复杂度均为O(log n)，和std::set完全一致
• 额外支持两个O(log n)复杂度的接口：
  • order_of_key(x)：返回集合中严格小于x的元素总数
  • find_by_order(k)：返回集合中排名第k的元素的迭代器
• 要统计区间[L, R]内的元素数量，直接计算order_of_key(R + 1) - order_of_key(L)即可，复杂度O(log n)

C++ 可用实现 #

GNU 编译器自带的 pbds 库已经提供了开箱即用的顺序统计树实现，无需自己造轮子，示例定义如下：

#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,
    std::less<T>,
    rb_tree_tag,
    tree_order_statistics_node_update
>;

使用方式和std::set几乎完全一致，直接调用接口即可完成区间计数。如果需要支持重复元素，把第二个模板参数null_type改成对应映射类型，或者给键值加冗余后缀即可。

2. 分块有序表 - 标准库可实现方案 #

如果你不想依赖非标准的pbds库，可以自己基于标准库实现分块有序表，复杂度满足你提到的优于O(n)的要求：

• 把所有元素分成大小约为√n的块，块之间整体有序，每个块内部用std::vector存储并保持有序
• 插入、删除时找到对应块，在块内做插入删除操作，块大小超出阈值时做拆分/合并，均摊复杂度O(√n)
• 统计区间元素数量时，两端的不完整块直接遍历计数，中间的完整块直接用std::lower_bound/std::upper_bound二分计算数量，总复杂度O(√n)

3. 树状数组/线段树 - 整数键场景最优 #

如果你的元素是整数、或者可以离散化映射到有限整数范围，树状数组（Fenwick Tree）或者线段树是性能最优的选择：

• 插入、删除、单元素查询、区间计数的复杂度均为O(log n)，实际运行速度比红黑树实现的顺序统计树快3~5倍
• 劣势是只能处理可离散化的键值，不支持自定义排序规则的任意对象。

关于标准库std::set不支持该功能的原因：C++标准并没有要求std::set实现顺序统计接口，红黑树本身增加子树计数的实现成本很低，也不会破坏现有迭代器失效规则，只是标准委员会没有将该功能纳入强制要求而已。

内容的提问来源于stack exchange，提问作者user5428643