我已经阅读了一些关于两种常见数据结构的教程，它们可以在O(lgn)内实现范围更新和查询:段树和二叉索引树(BIT/Fenwick tree)。
我找到的大多数例子都是关于一些结合和交换运算的，比如"整数在一个范围内的和"，"整数在一个范围内的异或"等等。
我想知道这两种数据结构(或者其他数据结构/算法，请提出)是否可以在O(lgn)内实现以下查询?(如果没有，那么O(sqrt N))
给定一个整数数组A，查询范围[l,r]
中不同整数的个数PS:假设可用整数的数量是~ 10^5，所以used[color] = true或bitmask是不可能的
例如: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^ 2n)时间内回答这些查询:只需对段树进行常规查询(遍历O(log n)个节点)并进行二分搜索以知道该节点中有多少个数字<= x(从这里额外O(log n))。
使用分数级联技术可以加速到O(log n)，这基本上允许你在每个节点上进行二进制搜索，而只在根节点上进行搜索。然而，它已经足够复杂，足以在文章中描述。
现在我们回到原来的问题。假设你有一个数组a_1，…, an。构建另一个数组b_1，…， b_n，其中b_i = a_i在数组中下一次出现的索引，如果是最后一次出现则为∞。
(1-indexed)例子:
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仍然可以提供帮助。
- 根据r值对查询进行排序。
- 为范围和查询[0,n]创建段树
-
对于输入数组中从左到右的每个值:
- 在段树的当前索引i处增加1。
-
对于当前元素，如果以前见过，则在
中减1在它之前的位置。 -
通过查询范围[l, r == i]中的sum来回答以当前索引i结束的查询。
简而言之就是继续标记向右的索引，即每个元素最近出现的位置，并将之前出现的位置设置为0。range的和将给出唯一元素的个数。
总时间复杂度为nLogn。
有一个众所周知的离线方法来解决这个问题。如果你有一个大小为n的数组，并对其进行q次查询，在每个查询中，你需要知道该范围内不同数字的计数然后你可以在O(n log n + q log n)的时间复杂度内解决整个问题。这类似于在O(log n)时间内解决每个查询。
让我们使用RSQ(Range sum query)技术来解决这个问题。对于RSQ技术，您可以使用段树或BIT。让我们讨论片段树技术。
要解决这个问题，您需要离线技术和段树。那么，什么是离线技术呢?脱机技术是指在脱机状态下做一些事情。在解决问题时，离线技术的一个例子是，您首先输入所有查询，然后重新排序，这是一种方法，以便您可以正确且轻松地回答它们，最后以给定的输入顺序输出答案。
解决方案的想法:
首先，接受测试用例的输入，并将给定的n个数字存储在一个数组中。设数组名称为array[]，输入q个查询并将其存储在向量v中，其中v的每个元素包含三个字段- l, r, idx。其中l是查询的起点，r是查询的终点，idx是查询的数量。比如这是第n次查询。现在根据查询的端点对向量v进行排序。假设我们有一个段树，它可以存储至少10^5个元素的信息。我们还有一个区域叫last[100005]。它存储数组[]中数字的最后一个位置。
最初，树的所有元素都是0，最后一个元素的所有元素都是-1。现在在数组[]上运行一个循环。现在在循环中，你需要检查数组[]的每个索引
last[array[i]]是否为-1 ?如果是-1，则写入last[array[i]]=i并调用update()函数，该函数将在段树的最后[array[i]]的第1个位置添加+1。如果last[array[i]]不是-1，则调用段树的update()函数，该函数将在段树的最后[array[i]]位置减去1或添加-1。现在您需要将当前位置存储为将来的最后一个位置。因此，您需要编写last[array[i]]=i并调用update()函数，该函数将在最后[array[i]]段树的第1个位置添加+1。
现在您必须检查查询是否在当前索引中完成。即如果(v[current].r==i)。如果这是真的，那么调用段树的query()函数，它将返回范围v[current]的和。L到v[电流]。R并将结果存储在v[电流]中。Idx ^答案[]数组的索引。您还需要将current的值增加1。6. 现在打印answer[]数组，其中包含按给定输入顺序排列的最终答案。
算法的复杂度为O(n log n)
给定的问题也可以用Mo's(离线)算法求解，也称为平方根分解算法。
总体时间复杂度为O(N*SQRT(N))。
参考mos-algorithm的详细解释，它甚至有复杂性分析和一个SPOJ问题可以用这种方法解决。
kd-trees在O(logn)内提供范围查询，其中n为点的个数。
如果你想要比kd-tree更快的查询，并且你愿意支付内存成本，那么Range树是你的朋友，它提供了一个查询:
0 (logdn + k)
，其中n为存储在树中的点的个数，d为每个点的维数，k为给定查询报告的点的个数。
宾利在这个领域是一个很重要的名字。:)