增长数组的范围最小查询 [英] 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) 时间内(经过一些预处理)完成每个查询?

I have an array A[0..n] and I need to find the minimum value in the interval A[k₀..n]. Based on that, the array is extended with a value A[n+1] and I need the minimum in A[k₁..n+1]. Again the array is extended with some A[n+2] and queried for the min in A[k₂..n+2]. Is there a way to do each query in O(1) time (after some preprocessing)?

与之前的这个问题相比:数组动态时的范围最小查询，不同之处在于查询的间隔从不同的位置开始k₀, k₁, k₂, ... 查询区间的末尾始终是数组的最右端.在我的应用程序中，我从一个空数组 (n=0) 开始，因此预处理可能很简单.如果这有帮助，在我的应用程序中，扩展中使用的新值始终为 1+(上次查询返回的最小值).但是位置 k₀, k₁, k₂, ... 取决于数组外的数据.

Compared with this earlier question: Range minimum queries when array is dynamic, a difference is that the queried interval start at varying positions k₀, k₁, k₂, ... The end of the queried interval is always the righmost end of the array. In my application I start with an empty array (n=0) so the preprocessing might be trivial. If this helps, in my application the new value used in the extension is always 1+(min returned by last query). But the positions k₀, k₁, k₂, ... depend on data outside of the array.

推荐答案

据我所知，没有办法在 O(1) 中同时添加新元素和查询，而且这可能是不可能的(尽管我不确定如何证明这一点).但是您可以使用 O(log(n)) 中轻松实现它>段树.对于任何实际应用来说，这可能已经足够了.

There is no way that I know of to make both the addition of a new element and the query happen in O(1), and it's probably impossible (though I'm not exactly sure how to prove this). But you can pretty easily make it happen in O(log(n)) using a segment tree. That's probably good enough for any practical application.

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