On O(n) – O(1) RMQ

Original link: https://www.shuizilong.com/house/archives/on-on-o1-rmq/

LCA and RMQ questions are closely related, and usually I think RMQ should be simpler than LCA, after all, the former is a question of sequence, but it seems that this is wrong?

The earliest O(n)-O(1) RMQ algorithm is converted into LCA and then done.

So the relationship between them may be more like the point set representation and coefficient representation of polynomials in FFT.

Although the classic algorithm of O(n)-O(1) RMQ has been heard of since I was very young (referring to the black book of lrj), but probably the fate is the same as the Fibonacci heap , Strassen Algorithm , etc., which belongs to theory something better but never written,

But recently I saw a very practical version based on block method, monotonic stack and bit operation, which is very simple to understand, and the constant is also very low!

Sparse Table is a very competitive algorithm for static RMQ, because the query time only needs O(1),

Here we consider using the large block method to reduce the complexity of preprocessing, usually block is generally b = sqrt(n), but here we can be smaller, let b = log(n) (because the preprocessing complexity of the ST algorithm is O(nlogn)).

Then the only problem is how to do O(1) for each block.

The simplest idea may be to run a small Sparse Table for each block. . .

But this will destroy our preprocessing complexity requirements, but the overall complexity is better, O(n/b*blogb). . (Then can we do it recursively?)

But there is a better way, which is to preprocess each position based on the monotone stack and then ask the width, the result will change.

And when this thing is queried, it can actually get the target position with direct bit operation O(1). . . So the problem is solved.

This article is transferred from: https://www.shuizilong.com/house/archives/on-on-o1-rmq/
This site is only for collection, and the copyright belongs to the original author.