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)?
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.
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 inO(log(n))using a segment tree. That's probably good enough for any practical application.