是否有像 C++ std set 这样的数据结构，它也可以快速 returns 范围内的元素数量？
Is there a data structure like a C++ std set which also quickly returns the number of elements in a range?
在C++中std::set（经常使用红黑二叉搜索树实现），元素自动排序，任意位置的key查找和删除取时间 O(log n) [摊销，即当大小对于当前容量来说太大时忽略重新分配].
在排序的 C++ 中 std::vector，查找也很快 （实际上可能比 std::set 快一点），但是插入很慢 （因为维护排序需要时间 O(n)）.
然而，排序的 C++ std::vectors 还有另一个 属性：它们可以快速找到一个范围内的元素数量（时间 O(log n)）.
即排序的 C++ std::vector 可以快速回答：给定的 x,y 之间有多少元素？
std::set 可以快速找到范围开始和结束的迭代器，但不知道范围内有多少元素。
那么，是否有一种数据结构可以实现 C++ std::set 的所有速度（快速查找和删除），而且还可以快速计算 给定范围内的元素数量？
（快速，我的意思是时间 O(log n)，或者可能是 log n 的多项式，甚至可能是 sqrt(n)。只要它比 O(n) 快，因为 O(n) 几乎与搜索所有内容的简单 O(n log n) 相同。
（如果不可能，即使对固定因子内的数字进行估计也是有用的。对于整数，一个微不足道的上限是 y-x+1，但如何获得下限? 对于具有排序的任意对象，没有这样的估计）。
编辑：我刚刚看到
related question，本质上是询问是否可以计算 前面元素的数量 。 （抱歉，之前没看到是我的错）。这显然等同于这个问题（要获得一个范围内的数字，只需计算 start/end 元素并减去，等等 ）
但是，与此处不同，该问题还允许计算一次数据然后固定数据，因此该问题 （以及排序向量答案） 实际上并不是一个这个的副本。
所有的数据结构都有其优缺点，标准库提供一堆容器的原因。
规则是修改的速度和数据提取的速度之间通常存在平衡。在这里，您想轻松访问一个范围内的元素数量。基于树的结构中的一种可能性是在每个节点中缓存其子树的元素数量。这将在每次插入或删除时添加平均 log(N) 操作（树的高度），但会大大加快范围内元素数量的计算。不幸的是，C++ 标准库中很少 类 是为推导量身定制的（而 AFAIK std::set 不是），因此您将不得不从头开始实现您的树。
也许您正在寻找 LinkedHashSet 替代 C++ https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html。
您要找的数据结构是Order Statistic Tree
它通常实现为二叉搜索树，其中每个节点额外存储其子树的大小。
不幸的是，我很确定 STL 没有提供。
在C++中std::set（经常使用红黑二叉搜索树实现），元素自动排序，任意位置的key查找和删除取时间 O(log n) [摊销，即当大小对于当前容量来说太大时忽略重新分配].
在排序的 C++ 中 std::vector，查找也很快 （实际上可能比 std::set 快一点），但是插入很慢 （因为维护排序需要时间 O(n)）.
然而，排序的 C++ std::vectors 还有另一个 属性：它们可以快速找到一个范围内的元素数量（时间 O(log n)）.
即排序的 C++ std::vector 可以快速回答：给定的 x,y 之间有多少元素？
std::set 可以快速找到范围开始和结束的迭代器，但不知道范围内有多少元素。
那么，是否有一种数据结构可以实现 C++ std::set 的所有速度（快速查找和删除），而且还可以快速计算 给定范围内的元素数量？
（快速，我的意思是时间 O(log n)，或者可能是 log n 的多项式，甚至可能是 sqrt(n)。只要它比 O(n) 快，因为 O(n) 几乎与搜索所有内容的简单 O(n log n) 相同。
（如果不可能，即使对固定因子内的数字进行估计也是有用的。对于整数，一个微不足道的上限是 y-x+1，但如何获得下限? 对于具有排序的任意对象，没有这样的估计）。
编辑：我刚刚看到 related question，本质上是询问是否可以计算 前面元素的数量 。 （抱歉，之前没看到是我的错）。这显然等同于这个问题（要获得一个范围内的数字，只需计算 start/end 元素并减去，等等 ）
但是，与此处不同，该问题还允许计算一次数据然后固定数据，因此该问题 （以及排序向量答案） 实际上并不是一个这个的副本。
所有的数据结构都有其优缺点，标准库提供一堆容器的原因。
规则是修改的速度和数据提取的速度之间通常存在平衡。在这里，您想轻松访问一个范围内的元素数量。基于树的结构中的一种可能性是在每个节点中缓存其子树的元素数量。这将在每次插入或删除时添加平均 log(N) 操作（树的高度），但会大大加快范围内元素数量的计算。不幸的是，C++ 标准库中很少 类 是为推导量身定制的（而 AFAIK std::set 不是），因此您将不得不从头开始实现您的树。
也许您正在寻找 LinkedHashSet 替代 C++ https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html。
您要找的数据结构是Order Statistic Tree
它通常实现为二叉搜索树，其中每个节点额外存储其子树的大小。
不幸的是，我很确定 STL 没有提供。