complexity of single change in array that is maintained with a static Range Minimum Query

Question

I had a test in the data structures course and one of the questions was:

lets say you have an n-size array that is maintained with a Range Minimum Query that gives the minimum between two numbers in the array in o(1) complexity. of course the array was o(n) prepared to answer the RMQ using dynamic programming for the different options. The question is - if i change one object (number) in the array, how would i change the preparations i did so that i can still find the RMQ in o(1), and what complexity will it take.

the answer is not making a new RMQ in o(n), it has to be less than that.

this question is not homework, i just want to go over the test to understand.

thanks in advance.

Answer 1

Store the index I and the new value V of the element changed.

On getting a query [L,R], check if L <= I <= R, if so return minimum of old_rmq(L,R) and V.

Answer 2

There are actually three types of algorithms for RMQ based on the complexity for update and query:

   Update     Query
1. O(N)       O(1)
2. O(1)       O(N)
3. O(logN)    O(logN)

The first and second type of algorithms are quite trivial to implement. First one involves storing values for all possible queries and thus answering them in O(1) time. Second one involves just updating the data-structure in O(1) time, but querying takes O(N). As per your question, it is not possible to have such a combination of yours.

However, the third type of algorithms are of particular interest. If you relax the condition that query can take O(logN) time, rather than O(1), you will also have an advantage, where in the overall running time remains constant, regardless of the number of updates and queries.

AFAIK, the best data structures used for getting such running times are Segment tree and Binary Indexed Trees