# RMQ

## Introduction¶

RMQ is the abbreviation of Range Maximum/Minimum Query, which means the maximum (minimum) value of an interval.

In the following descriptions, we assume that the uniform standard of initial array size is

## Monotonic stack¶

Since **OI wiki** already has a detailed description of monotonic stack, we will not get into details here.

Time Complexity:

Space Complexity:

## Sparse Table¶

Since **OI wiki** already has a detailed description of sparse table, we will not get into details here.

Time Complexity:

Space Complexity:

## Segment Tree¶

Since **OI wiki** already has a detailed description of segment tree, we will not get into details here.

Time Complexity:

Space Complexity:

## Four Russian¶

The Method of Four Russians is an algorithm based on ST table proposed by four Russian computer scientists.

The improvement made by the Four Russians algorithm, which is based on the ST table, is dividing a sequence into multiple blocks.

Specifically speaking, we divide the original array, let's call it array A, into blocks with equal length

For each block, we preprocess the elements within to get the minimum value of the block, then use these values to create an array B with a length of

At the same time, we also create a ST table for each fragmented block of array A.

When making queries, we can divide the query interval into no more than one continuous block interval of array B and no more than two continuous intervals within the entire block of array A. Obviously, these problems can be solved by interval query in the ST table.

When

Time complexity:

Space complexity:

Of course, because we need to run three ST tables, the constant of this method is relatively large.

Some minor algorithm optimizations

We found that when the two endpoints of a query belong to different blocks in array A, the query in the blocks of array A is about the prefix or suffix of each block.

Obviously, these queries can be solved within the time complexity of

In this way, we only need to perform the query operation on the ST table at most once.

Some algorithm optimizations[ONLY FOR REFERENCE]

Because the Four Russians algorithm is based on the ST table, and the competitive programming competition does not generally have a very strict requirement about time complexity, it can generally be replaced by the ST table(which is not very practical in algorithm competitions). Here we offer an improved version that is more practical in the contests.

We set the block size to

When querying, for those queries which the left and right endpoints are not in the same block, we can directly get the suffix RMQ of the block where left endpoint is located, the RMQ of the continuous block between the left and right endpoints, and the prefix RMQ of the block where right endpoint is located. The answer is the max/min value among the three.

For those queries which the left and right endpoints are in the same block, we can brute-force to find the RMQ between the two vertices. The time complexity is

In the competitive programming competitions, we don’t have to worry about the people in charge of creating problems abandon this algorithm, because we can fine-tune the block size randomly on the basis of

This is an algorithm that expects the time complexity to reach the lower bound, and the difficulty of the code implementation and time complexity constant are relatively small. So it is more practical in the algorithm competitions.

Note: The algorithm above refers to the solution of P3793 Yuno rescues grandpa (original post in Chinese).

## The application of Cartesian tree on RMQ¶

If you don't really know about Cartesian tree, please check out the description here 。

We find that the min/max value between two vertices on the original sequence is equal to the LCA weight of the two nodes on the Cartesian tree, which means that what we need to solve now is find the LCA between two nodes on the

How to find the LCA on the tree already has a description in the LCA section, so we will not get into details here.

What we need to use here is the LCA algorithm based on RMQ.

Some of you might be wondering: wait, why do we turn back to the RMQ question again?

Don't worry, let's find out the special nature of this RMQ problem:

Because the two adjacent nodes of the tree's dfs traversal sequence have the parent-child relationship, the depth difference between the two adjacent nodes is

Based on this feature, we can now improve the Four Russians algorithm.

Since the bottleneck of the Four Russian algorithm is the RMQ problem within the blocks, we focus on the optimization of it.

Because the difference between two adjacent numbers is

This suggests that we can preprocess the minimum value of all cases that do not exceed

During preprocessing, we need to preprocess the difference between two adjacent numbers in the same block, and use binary to represent it.

When querying, we can find the binary representation corresponding to the query interval, and look up the answer in the table.

In this way, the time complexity of Four Russians preprocessing is optimized to

Combining the Cartesian tree part, we can realize the RMQ problem in

The code and sample questions have already been given [here] (../graph/lca.md) in the LCA section, so we won't repeat it here.

Of course, due to the large number of conversion steps, the

If the data is random, we can also do a brute-force search on the Cartesian tree. The expected time complexity is

buildLast update and/or translate time of this article，Check the history

editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github

peopleContributor of this article OI-wiki

translateTranslator of this article Visit the original article!

copyrightThe article is available underCC BY-SA 4.0 & SATA; additional terms may apply.