arrays - 数组为动态时的范围最小查询

Question

我有一个数组，比如大小为 1 的 A(0 索引)。

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

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

比如说，我有 N 个查询。天真的方法将采用 O(N^2)。

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

NlogN复杂度甚至N有没有其他方法？

Answer 1

这里完全没有必要使用树这样的高级数据结构。只需一个简单的局部变量和列表即可完成所有工作:

创建一个空列表(比如 minList)。

从 end 索引开始，直到 initially given 数组的 start 索引，将最小值(直到该索引从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 = minimum(minList[k-1] + randomConstant, minElemAppended)

通过采用这种方法，

• 您不需要遍历给定数组的追加部分，甚至不需要遍历初始给定数组。
• 您可以选择根本不附加元素。
• 时间复杂度:O(N) 处理 N 个查询。
• 空间复杂度:O(N) 来存储 minList