Range minimum queries when array is dynamic

Question

I have an array say A(0 indexed) of size 1.

I want to find minimum in array A between indexes k1 (k1>=0) and A.size()-1(i.e the last element).

Then I would insert the value : (minimum element in given range + some "random" constant) at the end of the array.Then I have another query to find minimum between indexes k2 and A.size()-1. I find that, insert the value : (minimum in the given range + another "random" constant) at the end. I have to do many such queries.

Say, I have N queries. Naive approach would take O(N^2).

Cannot use segment trees as array is not static. But, a clever way to do is make segment tree for size N+1 array; beforehand and fill the unknown values with infinity. This would give me O(Nlog N) complexity.

Is there any other method for NlogN complexity or even N?

Answer 1

There is absolutely no need to use advanced data structures like tree here. Just a simple local variable and list will do it all:

Create an empty list(say minList).

Start from the end index and go till the start index of the initially given array, put the minimum values (till that index from the end) at the front of the list(i.e. do push_front).

Lets say the provided array is:

70 10 50 40 60 90 20 30

So the resultant minList will be:

10 10 20 20 20 20 20 30

After doing that, you only need to keep track of the minimum among newly appended elements in the continuously modifying array(say, minElemAppended).

Lets say you get k = 5 and randomConstant = -10, then

minElemAppended = minimum(minList[k-1] + randomConstant, minElemAppended)

By adopting this approach,

• You don't need to traverse the appended part of or even the initial given array.
• You have option not to append the elements at all.
• Time Complexity: O(N) to process N queries.
• Space Complexity: O(N) to store the minList