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

Question

我有一个大小为 1 的数组说 A(0 indexed)。

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

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

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

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

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

score 3 · Accepted Answer

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

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

从end索引开始，一直到最初给定start数组的索引，将最小值（直到从的索引）放在列表的前面（即 do ）。 endpush_front

假设提供的数组是：

70 10 50 40 60 90 20 30

所以结果minList将是：

10 10 20 20 20 20 20 30

之后，您只需要跟踪不断修改的数组（例如）中新添加minElemAppended的元素中的最小值。

假设你得到k = 5and randomConstant= -10，那么

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

通过采用这种方法，

1 回答 1