数组为动态时的范围最小查询
Range minimum queries when array is dynamic
我有一个数组，比如大小为 1 的 A（0 索引）。
我想在索引 k1 (k1>=0) 和 A.size()-1（即最后一个元素）之间找到数组 A 中的最小值。
然后我将在 array.Then 的末尾插入值：（给定范围内的最小元素 + 一些 "random" 常量）我有另一个查询来查找索引 k2 和 [= 之间的最小值24=]()-1。我发现，在末尾插入值：（给定范围内的最小值 + 另一个 "random" 常量）。我必须做很多这样的查询。
说，我有 N 个问题。天真的方法将采用 O(N^2)。
不能使用线段树，因为数组不是静态的。但是，一个聪明的方法是为大小为 N+1 的数组制作线段树；事先并用无穷大填充未知值。这会给我 O(Nlog N) 复杂度。
NlogN甚至N的复杂度还有其他方法吗？
这里完全没有必要使用树这样的高级数据结构。只需一个简单的局部变量和列表即可完成所有工作：
创建一个空列表（比如 minList）。
从 end 索引开始，直到 最初给定的 数组的 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 个查询。
- Space 复杂度：
O(N) 存储 minList
我有一个数组，比如大小为 1 的 A（0 索引）。
我想在索引 k1 (k1>=0) 和 A.size()-1（即最后一个元素）之间找到数组 A 中的最小值。
然后我将在 array.Then 的末尾插入值：（给定范围内的最小元素 + 一些 "random" 常量）我有另一个查询来查找索引 k2 和 [= 之间的最小值24=]()-1。我发现，在末尾插入值：（给定范围内的最小值 + 另一个 "random" 常量）。我必须做很多这样的查询。
说，我有 N 个问题。天真的方法将采用 O(N^2)。
不能使用线段树，因为数组不是静态的。但是，一个聪明的方法是为大小为 N+1 的数组制作线段树；事先并用无穷大填充未知值。这会给我 O(Nlog N) 复杂度。
NlogN甚至N的复杂度还有其他方法吗？
这里完全没有必要使用树这样的高级数据结构。只需一个简单的局部变量和列表即可完成所有工作：
创建一个空列表（比如 minList）。
从 end 索引开始，直到 最初给定的 数组的 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个查询。 - Space 复杂度：
O(N)存储minList