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

Правка en1, от jtnydv25, 2020-05-05 13:24:33

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?

#### История

Правки Rev. Язык Кто Когда Δ Комментарий
en1 jtnydv25 2020-05-05 13:24:33 1204 Initial revision (published)