# Bounds on update time in the RMQ problem subject to $O(1)$ query time?

In the static RMQ problem, one has to answer queries about the minimum in a range of a fixed array. A classic variation allows updates of the form $$A_i \leftarrow x$$.

My question is : How fast can we update if we must answer queries in $$O(1)$$?

I can think of a solution which works in $$O(\sqrt{n})$$ per update :

We can answer queries in $$O(1)$$ using a sparse table. Since each element is a part of $$O(n)$$ ranges in the sparse table, we can clearly update a sparse table of an array of size $$n$$ in $$O(n)$$. Now, divide into $$\sqrt{n}$$ blocks. For each block, maintain the prefix and suffix minimums and also a sparse table. Clearly, a block can be updated in $$O(\sqrt{n})$$. On the upper level, maintain another sparse table which can answer minimum over a range of blocks. Clearly this can also be done in $$O(\sqrt{n})$$ and the query time is still $$O(1)$$. The memory used and precomputation done are both $$O(n \log{n})$$.

Can we do better, say $$\text{polylog}(n)$$, perhaps using more memory and/or precomputation? Is there a known lower bound?

You can divide the whole range into $$n^{\frac{1}{3}}$$ blocks, and for each block apply your $$O\left(\sqrt{n}\right)$$ approach. Then you can get $$O\left(\sqrt{n^{\frac{2}{3}}}+n^{\frac{1}{3}}\right)=O\left(n^{\frac{1}{3}}\right)$$ update time with constant query time.
Recursively, you can get $$O\left(n^\epsilon\right)$$ update time with constant query time for any constant $$\epsilon>0$$.