问题
我有一个带有 N 个数字的数组。这些数字可能是不同的，也可能是无序的。我必须回答 Q 关于 A 和 B 之间有多少个不同数字的问题。其中 A、B 是数组<中 _x0030_="><= A <= B 之间的索引。长度。
我知道如何通过使用哈希表在每个查询中执行 O(N(，但我要求更有效的解决方案。我试图通过 sqrt 分解和段树来改进它，但我不能。我没有显示任何代码，因为我没有找到任何有效的想法。我正在寻找某人来解释更快的解决方案。
更新
我读到您可以收集查询，然后使用二叉索引树 (BIT( 回答所有查询。有人可以解释一下如何做到这一点。假设我知道 BIT 的工作原理。
对于每个索引i查找具有相同值的前一个索引prev[i](如果没有此类索引，则为 -1(。它可以在平均值中通过从左到右hash_map O(n)完成，那么索引范围 [l;r( 的答案是范围 [l;r( 中i元素的数量，使得它们的值小于 l(这需要一些思考，但应该很清楚(
现在我们将在数组prev上解决问题"给定范围[l;r)和值c找到小于c的元素数量"。如果我们在每个顶点中保存其范围(子树(中的所有数字，则可以使用段树O(log^2)完成。(在每个查询中，我们将获得O(log n)顶点并在其中进行二叉搜索(