是否可以查询O（lg N）范围内不同整数的数量？ [英] Is it possible to query number of distinct integers in a range in O(lg N)?

问题描述

我已经通读了一些有关两个常见数据结构的教程，可以在O（lg N）中实现范围更新和查询：细分树和二元索引树（BIT /分域树）。 / p>

我发现的大多数示例都是关于一些关联和交换运算的，例如范围内的整数之和，范围内的XOR整数等。

我想知道这两个数据结构（或任何其他数据结构/算法，请提出）是否可以在O（lg N）中实现以下查询？ （如果否，那么O（sqrt N）怎么样）

给出整数A的数组，查询范围[ l，r]

PS：假设可用整数的数量为〜10 ^ 5，因此已使用[ color] = true 或位掩码是不可能的

例如：A = [1,2,3,2,4,3,1 ]，query（[2,5]）= 3，其中范围索引从0开始。

解决方案

是的，即使您应该在线回答查询，也可以在O（log n）中进行。但是，这需要一些相当复杂的技术。

首先，让我们解决以下问题：给定一个数组，回答形式为多少个< = x是在索引[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）个）。

使用分数级联可以将速度提高到O（log n） a>技术，该技术基本上允许您不在每个节点中进行二进制搜索，而仅在根目录中进行。

现在我们回到原来的问题。假设您有一个数组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 。因此，问题归结为 [[，r]段中有多少个数字> r，这个问题被微不足道地简化为我上面描述的内容。

希望它帮助。

I have read through some tutorials about two common data structure which can achieve range update and query in O(lg N): Segment tree and Binary Indexed Tree (BIT / Fenwick Tree).

Most of the examples I have found is about some associative and commutative operation like "Sum of integers in a range", "XOR integers in a range", etc.

I wonder if these two data structures (or any other data structures / algorithm, please propose) can achieve the below query in O(lg N)? (If no, how about O(sqrt N))

Given an array of integer A, query the number of distinct integer in a range [l,r]

PS: Assuming the number of available integer is ~ 10^5, so used[color] = true or bitmask is not possible

For example: A = [1,2,3,2,4,3,1], query([2,5]) = 3, where the range index is 0-based.

解决方案

Yes, this is possible to do in O(log n), even if you should answer queries online. However, this requires some rather complex techniques.

First, let's solve the following problem: given an array, answer the queries of form "how many numbers <= x are there within indices [l, r]". This is done with a segment-tree-like structure which is sometimes called Merge Sort Tree. It is basically a segment tree where each node stores a sorted subarray. This structure requires O(n log n) memory (because there are log n layers and each of them requires storing n numbers). It is built in O(n log n) as well: you just go bottom-up and for each inner vertex merge sorted lists of its children.

Here is an example. Say 1 5 2 6 8 4 7 1 be an original array.

|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|

Now you can answer for those queries in O(log^2 n time): just make a reqular query to a segment tree (traversing O(log n) nodes) and make a binary search to know how many numbers <= x are there in that node (additional O(log n) from here).

This can be speed up to O(log n) using Fractional Cascading technique, which basically allows you to do the binary search not in each node but only in the root. However it is complex enough to be described in the post.

Now we return to the original problem. Assume you have an array a_1, ..., a_n. Build another array b_1, ..., b_n, where b_i = index of the next occurrence of a_i in the array, or ∞ if it is the last occurrence.

Example (1-indexed):

a = 1 3 1 2 2 1 4 1
b = 3 ∞ 6 5 ∞ 8 ∞ ∞

Now let's count numbers in [l, r]. For each unique number we'll count its last occurrence in the segment. With b_i notion you can see that the occurrence of the number is last if and only if b_i > r. So the problem boils down to "how many numbers > r are there in the segment [l, r]" which is trivially reduced to what I described above.

Hope it helps.

这篇关于是否可以查询O（lg N）范围内不同整数的数量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！