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 $$$. A good solution is segtree which solves it in $$$O(\log{n})$$$ query and update times. 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?