假设U是一组有序的元素，S⊆U，x∈U。S正在同时更新。 我想估计S中元素的数量小于 O(log(|S|(时间。
S由我无法更改的另一个软件组件维护。但是，每当将 e插入(或删除(到S中时，我都会收到一条消息e inserted (deleted). 我不想维护我自己的S版本，因为内存有限。 我正在寻找一个结构，ES，(也许使用 O(log(|S|(空间(，我可以在其中获得小于任何给定x的元素数量的合理估计。假设可以定期对整个集合S进行采样以重新创建或更新ES。
更新：我认为这个问题陈述必须包含U的更具体值。 一个明显的例子是U是数字(整数、双精度等(。另一种情况是U是按字典顺序排序的字符串。
在数字的情况下，可以使用概率分布(但如何确定呢？
我想知道是否可以定期扫描集合S。 将整个集合放入数组中并进行排序。 然后选择 log(n( 值 n/log(n(， 2n/log(n( ...n 其中 n = |S|. 然后根据这些值绘制直方图？
更一般地说，如何从S中找到适当的概率分布？
不确定按字典顺序排列的字符串的度量单位是什么？
同时，我假设你的意思是线程安全的。在这种情况下，我相信您正在寻找的是ConcurrentSkipListSet，它本质上是一个并发TreeSet。 您可以使用ConcurrentSkipListSet#headSet.size()或ConcurrentSkipListSet#tailSet.size()来获取大于/小于(或等于(单个元素的元素数量，您可以在其中传入自定义Comparator。
x是常数吗？如果是这样，在插入和删除数字时跟踪小于x的数字似乎很容易？
如果x不是常数，您仍然可以采用直方图方法。划分值可以采用的范围。插入/删除项目时，请跟踪每个范围存储桶中的项目数。获取查询时，汇总较小存储桶中的所有值。
我接受你的观点，即分桶很棘手 - 特别是如果您对底层数据一无所知。您可以记录x的前 100 个值，并使用这些值计算平均值和标准差。然后，您可以假设值呈正态分布，并以这种方式计算存储桶。
显然，如果您更了解基础数据，则可以使用不同的分布模型。如果您希望模块化方法是通用的，那么使用模块化方法将很容易。