jtnydv25's blog

By jtnydv25, history, 3 years ago,

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?

• +90

 » 3 years ago, # |   +2 Updating the block sparse table, or the upper level sparse table, runs in $O(\sqrt{n} \log(n))$, not in $O(\sqrt{n})$.You approach reminds me a little of the Sqrt Tree by gepardo. That one does updates in true $O(\sqrt{n})$ and still answers queries in $O(1)$. And as a bonus it supports more complex operations than computing the maximum, like computing the sum in a range, for which the sparse table cannot compute the answer in $O(1)$. You can learn about it, see here or here
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 The second link contains also an idea, how to improve it even further with less precomputing/memory, $O(n \log^* n)$, so almost $O(n)$, if you can overlap ranges like you can do with min/max queries. I'm not 100% sure, but I think updates are still $O(\sqrt{n})$ though.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +15 Each element is a part of $O(n)$ ranges in the sparse table of an array with $n$ entries. Proof : For the range $[j, j + 2^k - 1]$ to contain $i$, $i - 2^{k} + 1 \leq j \leq i$. So there are $\leq 2^k$ ranges of length $2^k$ that require a change. Summing up gives $O(n)$. Another way to see this is to subtract the left and right parts to get $n \log{n} - i \log{i} - (n-i) \log{(n-i)} = O(n)$So, the upper level sparse table takes $O(\sqrt{n})$ per update.Anyway, I also posted this on stackexchange, and as the answer says, we can recursively get $O(n^{\epsilon})$ for any constant $\epsilon > 0$, which is really cool.The possibility of a polylogarithmic update time is still a question though!
•  » » » 3 years ago, # ^ |   0 Oh, right. You are correct.Have you looked at the idea in the second article? It might have polylog updates. Basically splits the array into $log(n)$ segments, and do the same thing for each block recursively. And it keeps a sparse table for all every block in every layer. But I haven't read the article for a long time, so I don't understand all the details right now.
 » 3 years ago, # |   +16 Well... I don't think that's what you want, but you can get $O(k n^{\frac{2}{k}})$ for any fixed $k$.Let's build $k$-layer structure, $i$-th layer is divided into blocks of length $n^{\frac{i}{k}}$, each block is a union of $n^{\frac{1}{k}}$ blocks on previous layer. Each block stores minima on all $O((n^{\frac{1}{k}})^{2})$ segments of blocks of previous layer.I think you get the idea. Update is $O(k n^{\frac{2}{k}})$, get is $O(k)$ which is $O(1)$ for fixed $k$. With $k = \log n$ you get the segment tree.