回答有关给定范围内不同数字数量的查询
Answer queries about the number of distinct numbers in a given range
问题
我有一个包含 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) 的答案是范围 [l;r 中的元素数 i ) 使得它们的值小于 l （这需要一些思考但应该清楚）
现在我们将解决数组 prev 上的问题 "given range [l;r) and value c find number of elements that are less then c"。如果我们在每个顶点中保存其范围（子树）中的所有数字，则可以使用线段树在 O(log^2) 中完成。 （在每个查询中，我们将获得 O(log n) 个顶点并在其中进行二分查找）
问题
我有一个包含 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) 的答案是范围 [l;r 中的元素数 i ) 使得它们的值小于 l （这需要一些思考但应该清楚）
现在我们将解决数组 prev 上的问题 "given range [l;r) and value c find number of elements that are less then c"。如果我们在每个顶点中保存其范围（子树）中的所有数字，则可以使用线段树在 O(log^2) 中完成。 （在每个查询中，我们将获得 O(log n) 个顶点并在其中进行二分查找）