问题
我有一个包含 N 个数字的数组。这些数字可能是不同的，也可能是无序的。我必须回答关于 A 和 B 之间有多少个不同数字的 Q 查询。其中 A、B 是 0 <= A <= B < array.Length 之间的索引。
我知道如何使用 HashTable 为每个查询完成 O(N)，但我要求更有效的解决方案。 我试图用 sqrt 分解和线段树来改进它，但我做不到。我没有展示任何代码，因为我没有找到任何可行的想法。 我正在找人解释更快的解决方案。
更新
我读到您可以收集查询，然后使用二叉索引树 (BIT) 回答所有问题。有人可以解释如何去做。假设我知道 BIT 是如何运作的。
最佳答案
对于每个索引 i，找到具有相同值的前一个索引 prev[i](如果没有这样的索引，则为 -1)。它可以通过使用 hash_map 从左到右在 O(n) 平均时间内完成，然后索引范围 [l;r) 的答案是 i 中的元素数范围 [l;r) 使得它们的值小于 l (这需要一些思考但应该清楚)
现在我们将解决问题“给定范围 [l;r) 和值 c 找到小于 c 的元素数”在数组 prev 上。如果我们在每个顶点中保存其范围(子树)中的所有数字，则可以使用线段树在 O(log^2) 中完成。 (在每个查询中，我们将获得 O(log n) 个顶点并在其中进行二分查找)
关于algorithm - 回答有关给定范围内不同数字数量的查询，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48134696/