增长数组的范围最小查询
Range Minimum Query for growing array
我有一个数组A[0..n]，我需要找到区间A[k₀..n]中的最小值。基于此，数组扩展了一个值 A[n+1]，我需要 A[k₁..n+1] 中的最小值。再次用一些 A[n+2] 扩展数组并查询 A[k2..n+2] 中的最小值。有没有办法在 O(1) 时间内完成每个查询（经过一些预处理后）？
与前面的问题相比，不同的是查询的区间从不同的位置k₀, k₁, k₂, ...大批。在我的应用程序中，我从一个空数组 (n=0) 开始，因此预处理可能很简单。如果这有帮助，在我的应用程序中，扩展中使用的新值始终为 1+（上次查询返回的最小值）。但是位置 k₀, k₁, k₂, ... 取决于数组外的数据。
据我所知，无法在 O(1) 中同时添加新元素和进行查询，这可能是不可能的（尽管我不确定如何证明这一点） .但是您可以很容易地使用 segment tree 在 O(log(n)) 中实现它。对于任何实际应用来说，这可能已经足够了。
我有一个数组A[0..n]，我需要找到区间A[k₀..n]中的最小值。基于此，数组扩展了一个值 A[n+1]，我需要 A[k₁..n+1] 中的最小值。再次用一些 A[n+2] 扩展数组并查询 A[k2..n+2] 中的最小值。有没有办法在 O(1) 时间内完成每个查询（经过一些预处理后）？
与前面的问题
据我所知，无法在 O(1) 中同时添加新元素和进行查询，这可能是不可能的（尽管我不确定如何证明这一点） .但是您可以很容易地使用 segment tree 在 O(log(n)) 中实现它。对于任何实际应用来说，这可能已经足够了。