TreeSet：有效地小于一个值的元素数

Question

我需要一种TreeSet真正快速地计算小于Integers中的X的元素数的方法。

我可以用

• subSet（）
• 耳机（）
• tailSet（）

方法，但它们确实很慢（我只需要计数，而不是数字本身）。有办法吗？

谢谢。

---

编辑：

我发现了一种变通方法，可以使事情更快！我正在使用BitSet及其cardinality（）方法。我首先创建一个BitSet，然后为添加到TreeSet中的每个元素设置BitSet中的相应索引。现在，要计算少于XI的元素数量，请使用：

bitset.get（0，X + 1）.cardinality（）

与treeset.subSet（0，true，X，true）.size（）相比，这要快得多。

有人知道为什么吗？我假设BitSet.cardinality（）不使用线性搜索。

Answer 1

如果不更新数据结构，就在hashmap中保留小于X的元素个数即可！

如果您不经常更新，请保留一个排序的数字链接列表。在插入/删除时，以 O(1) 的时间从列表中添加/删除并更新哈希图 (O(n))。

通过使用（排序的）二叉树，您可以进行 O(Log(n)) 获取和 O(Log(n)) 更新。在树的每个元素中，还保留其后代的数量。现在要获得 # items < than y，您可以在二叉树中找到它，而且每当您向右而不是向左移动时，也会对元素数量进行求和。更新时，您还需要更新新元素的祖先。

顺便说一句，如果您愿意接受近似答案，也可能有更快的方法。