1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.