我已经阅读了一些关于可以在 O(lg N) 中实现范围更新和查询的两种常见数据结构的教程：段树和二进制索引树（BIT / Fenwick Tree）。
我发现的大多数示例都是关于一些关联和交换操作，例如“范围内的整数之和”、“范围内的 XOR 整数”等。
我想知道这两个数据结构（或任何其他数据结构/算法，请提出）是否可以在O（lg N）中实现以下查询？（如果不是，那么 O(sqrt N) 怎么样）
给定一个整数数组 A，查询范围 [l,r] 中不同整数的个数
PS：假设可用整数的数量为〜10 ^ 5，所以 used[color] = true或位掩码是不可能的
例如：A = [1,2,3,2,4,3,1], query([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”，这被简单地简化为我上面描述的内容。
希望能帮助到你。
如果您愿意离线回答查询，那么普通的旧段树/ BIT 仍然可以提供帮助。
对于输入数组中的每个值，从左到右：
对于当前元素，如果之前见过，则
在其先前位置的段树中减 1。
通过查询范围 [l, r == i] 中的总和来回答以当前索引 i 结尾的查询。
简而言之，这个想法是继续标记向右的索引，每个单独元素的最新出现，并将以前的出现设置回 0。范围的总和将给出唯一元素的计数。
总体时间复杂度再次为 nLogn。
有一种众所周知的离线方法可以解决这个问题。如果您有 n 个大小的数组和 q 个查询，并且在每个查询中，您需要知道该范围内不同数字的计数，那么您可以在 O(n log n + q log n) 时间复杂度内解决整个问题。这类似于在 O(log n) 时间内解决每个查询。
让我们使用 RSQ（范围求和查询）技术来解决这个问题。对于 RSQ 技术，您可以使用分段树或 BIT。让我们讨论分段树技术。
为了解决这个问题，您需要一种离线技术和一个分段树。现在，什么是离线技术？离线技术是离线做某事。在解决问题时，离线技术的一个例子是，您首先输入所有查询，然后对它们重新排序，这样您就可以正确轻松地回答它们，最后以给定的输入顺序输出答案。
解决思路：
首先，获取测试用例的输入并将给定的 n 个数字存储在一个数组中。让数组名称为array[]，并接受输入q个查询并将它们存储在向量v中。其中v的每个元素都包含三个字段-l、r、idx。其中 l 是查询的起点，r 是查询的终点，idx 是查询的数量。像这个是第 n^th 查询。现在根据查询的端点对向量 v 进行排序。让我们有一个线段树，它可以存储至少 10^5 个元素的信息。我们还有一个名为 last[100005] 的区域。它存储数组[]中数字的最后一个位置。
最初，树的所有元素都是零，最后的所有元素都是 -1。现在在数组 [] 上运行一个循环。现在在循环中，您必须检查数组 [] 的每个索引的这个东西。
last[array[i]] 是否为-1？如果为-1，则写入last[array[i]]=i 并调用update() 函数，该函数将在分段树的last[array[i]] 位置添加+1。如果 last[array[i]] 不是 -1，则调用段树的 update() 函数，该函数将在段树的 last[array[i]] 位置减去 1 或添加 -1。现在您需要将当前位置存储为将来的最后位置。因此您需要编写 last[array[i]]=i 并调用 update() 函数，该函数将在分段树的 last[array[i]] th 位置添加 +1。
现在您必须检查当前索引中的查询是否完成。即 if(v[current].r==i)。如果这是真的，那么调用段树的 query() 函数，它将返回范围 v[current].l 到 v[current].r 的总和，并将结果存储在 v[current].idx^th 的索引中答案[] 数组。您还需要将 current 的值增加 1。 6. 现在以给定的输入顺序打印包含您最终答案的 answer[] 数组。
该算法的复杂度为 O(n log n)。
给定的问题也可以使用 Mo 的（离线）算法（也称为平方根分解算法）来解决。
总体时间复杂度为 O(N*SQRT(N))。
详细解释请参考mos-algorithm，它甚至有复杂性分析和可以用这种方法解决的 SPOJ 问题。