The dynamic RMQ problem goes as follows:
Given an array of integers $$$a$$$ of length $$$n$$$ and $$$q$$$ queries of $$$2$$$ types:
- $$$l\ r$$$ — find the minimum on $$$a[l..r]$$$
- $$$i\ x$$$ — make $$$a_i = x$$$
If the number of updates $$$\gt \gt$$$ the number of queries (which may occur in MO algorithm for example, where we can have $$$O(n)$$$ min queries and $$$O(n\sqrt n) $$$ updates), what is the most efficient way to solve the problem?
We obviously need smth faster than $$$O(\log(n) )$$$ per update (which is achievable with a ton of ways), like $$$O(1)$$$ or maybe $$$O(\log{\log{n} }) $$$.
I though about it for a while but wasn't able to come up even with sublinear solution for querying min while preserving $$$O(1)$$$ update time.
