Range Minimum Query for growing array

Question

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.

Mark Saving · Accepted Answer · 2021-05-30 22:26:29Z

2

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.

answered May 30, 2021 at 22:26

Mark Saving

1,8179 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Range Minimum Query for growing array

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related