是否可以查询 O(lg N) 范围内不同整数的数量？
Is it possible to query number of distinct integers in a range in O(lg N)?
我已经阅读了一些教程，介绍了两种可以在 O(lg N) 中实现范围更新和查询的常见数据结构：Segment tree and Binary Indexed Tree (BIT / Fenwick Tree)。
我找到的大多数例子都是关于一些关联和交换运算的，比如“一个范围内的整数之和”、“一个范围内的整数异或”等
请问这两种数据结构（或其他任何数据结构/算法，请提出）是否可以在O(lg N)中实现以下查询？ (如果不是，O(sqrt N)怎么样)
给定一个整数数组A，查询范围[l,r][=12=中不同整数的个数]
PS：假设可用整数的数量是~10^5，所以used[color] = true或位掩码是不可能的
例如：A = [1,2,3,2,4,3,1], query([2,5]) = 3，其中范围索引从0开始。
kd-trees在O(logn)中提供范围查询，其中n是点数。
如果您想要比 kd-tree 更快的查询，并且愿意支付内存成本，那么 Range trees 是您的朋友，提供以下查询：
O(logdn + k)
其中 n 是存储在树中的点数，d 是每个点的维度，k 是给定查询报告的点数。
宾利在这个领域是一个重要的名字。 :)
是的，这可以在 O(log n) 中完成，即使您应该在线回答问题。然而，这需要一些相当复杂的技术。
首先，让我们解决以下问题：给定一个数组，回答 "how many numbers <= x are there within indices [l, r]" 形式的查询。这是通过类似于段树的结构完成的，有时称为合并排序树。它基本上是一个线段树，其中每个节点存储一个排序的子数组。这种结构需要 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)）。
这可以使用 Fractional Cascading 技术加速到 O(log n)，这基本上允许您不在每个节点中而是仅在根节点中进行二进制搜索。然而，它足够复杂，可以在 post.
中进行描述
现在我们return回到原来的问题。假设您有一个数组 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 时数字的出现是最后一次。所以问题归结为 "how many numbers > r are there in the segment [l, r]" 这被简单地简化为我上面描述的内容。
希望对您有所帮助。
给定的问题也可以使用 Mo 的（离线）算法解决，也称为平方根分解算法。
整体时间复杂度为 O(N*SQRT(N))。
详细解释参考mos-algorithm，它甚至有复杂性分析和一个SPOJ问题可以用这种方法解决。
如果您愿意离线回答查询，那么普通的旧线段树/BIT 仍然可以提供帮助。
- 根据 r 值对查询进行排序。
- 为范围和查询[0, n]制作线段树
对于输入数组中的每个值，从左到右：
- 在线段树中的当前索引 i 处加 1。
当前元素，如果之前见过，则减1 in
段树在它之前的位置。
通过查询 [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。
现在 运行 数组 [] 上的一个循环。现在在循环中，你必须检查 array[].
的每个索引的这个东西
last[array[i]] 是否为-1？如果它是 -1 则写入 last[array[i]]=i 并调用其 update() 函数将在线段树的 last[array[i]] th 位置添加 +1 。
如果 last[array[i]] 不是 -1 则调用线段树的 update() 函数，它将在线段树的 last[array[i]] th 位置减去 1 或添加 -1 。现在您需要将当前位置存储为未来的最后位置。因此您需要编写 last[array[i]]=i 并调用 update() 函数，该函数将在线段树的 last[array[i]] th 位置添加 +1。
现在您必须检查当前索引中的查询是否已完成。即 if(v[current].r==i)。如果这是真的，则调用线段树的 query() 函数，它将 return 和范围 v[current].l 到 v[current].r 的总和并将结果存储在 v[current].idx 中answer[] 数组的第 ^ 个索引。您还需要将 current 的值增加 1。
6. 现在打印包含给定输入顺序的最终答案的 answer[] 数组。
算法的复杂度为O(n log n)。
我已经阅读了一些教程，介绍了两种可以在 O(lg N) 中实现范围更新和查询的常见数据结构：Segment tree and Binary Indexed Tree (BIT / Fenwick Tree)。
我找到的大多数例子都是关于一些关联和交换运算的，比如“一个范围内的整数之和”、“一个范围内的整数异或”等
请问这两种数据结构（或其他任何数据结构/算法，请提出）是否可以在O(lg N)中实现以下查询？ (如果不是，O(sqrt N)怎么样)
给定一个整数数组A，查询范围[l,r][=12=中不同整数的个数]
PS：假设可用整数的数量是~10^5，所以used[color] = true或位掩码是不可能的
例如：A = [1,2,3,2,4,3,1], query([2,5]) = 3，其中范围索引从0开始。
kd-trees在O(logn)中提供范围查询，其中n是点数。
如果您想要比 kd-tree 更快的查询，并且愿意支付内存成本，那么 Range trees 是您的朋友，提供以下查询：
O(logdn + k)
其中 n 是存储在树中的点数，d 是每个点的维度，k 是给定查询报告的点数。
宾利在这个领域是一个重要的名字。 :)
是的，这可以在 O(log n) 中完成，即使您应该在线回答问题。然而，这需要一些相当复杂的技术。
首先，让我们解决以下问题：给定一个数组，回答 "how many numbers <= x are there within indices [l, r]" 形式的查询。这是通过类似于段树的结构完成的，有时称为合并排序树。它基本上是一个线段树，其中每个节点存储一个排序的子数组。这种结构需要 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)）。
这可以使用 Fractional Cascading 技术加速到 O(log n)，这基本上允许您不在每个节点中而是仅在根节点中进行二进制搜索。然而，它足够复杂，可以在 post.
中进行描述现在我们return回到原来的问题。假设您有一个数组 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 时数字的出现是最后一次。所以问题归结为 "how many numbers > r are there in the segment [l, r]" 这被简单地简化为我上面描述的内容。
希望对您有所帮助。
给定的问题也可以使用 Mo 的（离线）算法解决，也称为平方根分解算法。
整体时间复杂度为 O(N*SQRT(N))。
详细解释参考mos-algorithm，它甚至有复杂性分析和一个SPOJ问题可以用这种方法解决。
如果您愿意离线回答查询，那么普通的旧线段树/BIT 仍然可以提供帮助。
- 根据 r 值对查询进行排序。
- 为范围和查询[0, n]制作线段树
对于输入数组中的每个值，从左到右：
- 在线段树中的当前索引 i 处加 1。
当前元素，如果之前见过，则减1 in
段树在它之前的位置。通过查询 [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。 现在 运行 数组 [] 上的一个循环。现在在循环中，你必须检查 array[].
的每个索引的这个东西last[array[i]] 是否为-1？如果它是 -1 则写入 last[array[i]]=i 并调用其 update() 函数将在线段树的 last[array[i]] th 位置添加 +1 。 如果 last[array[i]] 不是 -1 则调用线段树的 update() 函数，它将在线段树的 last[array[i]] th 位置减去 1 或添加 -1 。现在您需要将当前位置存储为未来的最后位置。因此您需要编写 last[array[i]]=i 并调用 update() 函数，该函数将在线段树的 last[array[i]] th 位置添加 +1。
现在您必须检查当前索引中的查询是否已完成。即 if(v[current].r==i)。如果这是真的，则调用线段树的 query() 函数，它将 return 和范围 v[current].l 到 v[current].r 的总和并将结果存储在 v[current].idx 中answer[] 数组的第 ^ 个索引。您还需要将 current 的值增加 1。 6. 现在打印包含给定输入顺序的最终答案的 answer[] 数组。
算法的复杂度为O(n log n)。