sho*_*ole 12 algorithm data-structures fenwick-tree segment-tree
我已经阅读了一些关于两个常见数据结构的教程,这些数据结构可以在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开始的.
Iva*_*nov 13
是的,即使您应该在线回答查询,也可以在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。