Bounds on update time in the RMQ problem subject to $O(1)$ query time?
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&gt;0$.