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.
not most effective for MO algorithm
split in blocks of length log log n, store minimum in each
to update you naively recalculate minimum in the block
then you can answer in O(n / log log n), update in O(log log n)
you are welcome
you can also do O(log log log n) by the way
O(1) I dont know though