动态数组时范围最小查询 [英] Range minimum queries when array is dynamic

问题描述

我有一个数组，说大小为1的A（0索引）。

我想在数组A中找到索引k1（k1> = 0）与最小值之间的最小值A.size（）-1（即最后一个元素）。

然后我将在数组的末尾插入值：（给定范围内的最小元素+一些随机常数）。然后，我有另一个查询来查找最小值在索引k2和A.size（）-1之间。我发现，在末尾插入值：（最小值在给定范围内+另一个随机常量）。我必须做很多这样的查询。

说，我有N个查询。天真的方法需要O（N ^ 2）。

不能使用段树，因为数组不是静态的。但是，一个聪明的方法是为N + 1大小的数组制作段树。事先用无穷大填充未知值。这会给我O（Nlog N）的复杂度。

是否还有其他方法可以解决NlogN复杂度甚至是N？

解决方案

这里绝对不需要使用像tree这样的高级数据结构。只需一个简单的局部变量和列表即可完成所有操作：

创建一个空列表（例如 minList ）。 / p>

从结束索引开始，直到开始 最初给出的数组的索引，将最小值（直到 end 的索引）放在列表​​的前面（即 push_front ）。

可以说提供的数组是：

  70 10 50 40 60 90 20 30 
  

因此生成的 minList 将是：

  10 10 20 20 20 20 20 30 
  

完成此操作后，您只需仅跟踪连续修改数组中新添加的元素中的最小值（例如， minElemAppended ）。

假设您获得 k = 5 和 randomConstant = -10，然后

  minElemAppended =最小值（minList [k-1] + randomConstant，minElemAppended）
  

通过采用这种方法，

• 您不需要遍历附加数组甚至是初始给定数组。


• 您拥有选项完全不附加元素。


• 时间复杂度： O（N）处理 N 查询。


• Space Co复杂性： O（N）存储 minList

I have an array say A(0 indexed) of size 1.

I want to find minimum in array A between indexes k1 (k1>=0) and A.size()-1(i.e the last element).

Then I would insert the value : (minimum element in given range + some "random" constant) at the end of the array.Then I have another query to find minimum between indexes k2 and A.size()-1. I find that, insert the value : (minimum in the given range + another "random" constant) at the end. I have to do many such queries.

Say, I have N queries. Naive approach would take O(N^2).

Cannot use segment trees as array is not static. But, a clever way to do is make segment tree for size N+1 array; beforehand and fill the unknown values with infinity. This would give me O(Nlog N) complexity.

Is there any other method for NlogN complexity or even N?

解决方案

There is absolutely no need to use advanced data structures like tree here. Just a simple local variable and list will do it all:

Create an empty list(say minList).

Start from the end index and go till the start index of the initially given array, put the minimum values (till that index from the end) at the front of the list(i.e. do push_front).

Lets say the provided array is:

70 10 50 40 60 90 20 30

So the resultant minList will be:

10 10 20 20 20 20 20 30

After doing that, you only need to keep track of the minimum among newly appended elements in the continuously modifying array(say, minElemAppended).

Lets say you get k = 5 and randomConstant = -10, then

minElemAppended = minimum(minList[k-1] + randomConstant, minElemAppended)

By adopting this approach,

• You don't need to traverse the appended part of or even the initial given array.
• You have option not to append the elements at all.
• Time Complexity: O(N) to process N queries.
• Space Complexity: O(N) to store the minList

这篇关于动态数组时范围最小查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！