algorithm - 回答有关给定范围内不同数字数量的查询

Question

问题

我有一个包含 N 个数字的数组。这些数字可能是不同的，也可能是无序的。我必须回答关于 A 和 B 之间有多少不同数字的 Q 查询。其中 A、B 是 0 <= A <= B < array.Length 之间的索引。

我知道如何通过使用 HashTable 来完成每个查询的 O(N)，但我要求更有效的解决方案。我试图通过 sqrt 分解和分段树来改进它，但我做不到。我没有显示任何代码，因为我没有找到任何可行的想法。我正在找人解释更快的解决方案。

更新

我读到您可以收集查询，然后使用二进制索引树 (BIT) 来回答所有问题。有人可以解释如何做到这一点。假设我知道 BIT 是如何工作的。

Answer 1

对于每个索引，i找到prev[i]具有相同值的前一个索引（如果没有这样的索引，则为 -1）。它可以通过O(n)使用 hash_map 从左到右平均完成，然后索引范围 [l;r) 的答案是范围 [l;r) 中的元素数，i使得它们的值小于那时l（它需要一些思考，但应该清楚）

现在我们将在数组上解决“给定范围[l;r)和值c查找小于的元素数量”的问题。如果我们在每个顶点中保存其范围（子树）内的所有数字，则可以使用线段树来完成。（在每个查询中，我们将获得顶点并在其中进行二分搜索）cprevO(log^2)O(log n)