我已经阅读了一些关于两个常见数据结构的教程，它们可以在O（lg N）中实现范围更新和查询： 细分树 和 二进制索引树 （BIT / Fenwick树）。
我发现的大多数例子都是关于一些关联和交换操作，如“范围内的整数和”，“范围内的XOR整数”等。
我想知道这两个数据结构（或任何其他数据结构/算法，请提出）是否可以在O（lg N）中实现以下查询？ （如果不是，O（sqrt N）怎么样）
给定一个整数A的数组，查询范围[l，r]中的不同整数的数量
PS：假设可用整数的数量是~10 ^ 5，那么 used[color] = true 或位掩码是不可能的
例如：A = [1,2,3,2,4,3,1]，查询（[2,5]）= 3，其中范围索引是从0开始的。
是的，即使您应该在线回答查询，也可以在O（log n）中执行此操作。但是，这需要一些相当复杂的技术。
首先，让我们解决以下问题：给定一个数组，回答“索引[l，r]中有多少个数<= x'的形式的查询”。这是通过一种类似于树的结构来完成的，有时也称为合并排序树。它基本上是一个分段树，其中每个节点存储一个已排序的子阵列。这种结构需要O（n log n）内存（因为有log n层，每个都需要存储n个数字）。它也是在O（n log n）中构建的：你只需要自下而上，并为每个内部顶点合并其子项的排序列表。
这是一个例子。说 1 5 2 6 8 4 7 1 是一个原始数组。
|1 1 2 4 5 6 7 8|
|1 2 5 6|1 4 7 8|
|1 5|2 6|4 8|1 7|
|1|5|2|6|8|4|7|1|
现在你可以用O（log ^ 2 n时间）回答那些查询：只需对段树进行重新查询（遍历O（log n）节点）并进行二进制搜索以知道有多少个数字<= x在该节点中（此处附加O（log n））。
这可以加速到O（log n）使用 分数级联 技术，它基本上允许您不在每个节点中进行二进制搜索，而只在根中进行。然而，它很复杂，可以在帖子中描述。
现在我们回到原来的问题。假设你有一个数组a_1，...，a_n。构建另一个数组b_1，...，b_n，其中b_i =数组中下一次出现a_i的索引，如果是最后一次出现则为∞。
示例（1索引）：
a = 1 3 1 2 2 1 4 1
b = 3 ∞ 6 5 ∞ 8 ∞ ∞
现在让我们计算[l，r]中的数字。对于每个唯一编号，我们将计算其在段中的最后一次出现。使用b_i概念，您可以看到数字的出现是最后的，当且仅当 b_i > r。所以问题归结为“段[l，r]中存在多少个数> r，这可以简单地减少到我上面所描述的内容。
希望能帮助到你。
给定的问题也可以使用Mo（离线）算法（也称为平方根分解算法）来解决。
总时间复杂度为O（N * SQRT（N））。
参考 MOS-算法对于详细解释，它甚至具有复杂性分析和SPOJ问题，可以通过这种方法解决。
KD树 在O（logn）中提供范围查询，其中n是点数。
如果你想要比kd树更快的查询，并且你愿意支付内存成本，那么 范围树木 是你的朋友，提供以下查询：
O（日志dn + k）
其中n是树中存储的点数，d是每个点的维数，k是给定查询报告的点数。
宾利是这个领域的重要名称。 :)