Search code examples
arraysalgorithmdata-structuresrmqcartesian-tree

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

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.

Solution

  • 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.