RMQ

Introduction

RMQ is short for Range Maximum/Minimum Query, which asks for the maximum or minimum value in an interval.

In what follows, assume that the initial array has size $n$ and that there are $m$ queries.

In what follows, the time complexity is written as $O(A) \sim O(B)$, where $O(A)$ denotes the preprocessing time complexity and $O(B)$ denotes the time complexity of a single query.

Monotonic stack

This part is already covered in OI Wiki, so only a link is provided here; we do not elaborate further.

The time complexity is $O(m\log m) \sim O(\log n)$, and the space complexity is $O(n)$.

Sparse table

Because OI Wiki already describes this part, we provide only a link and omit further discussion.

The time complexity is $O(n\log n) \sim O(1)$, and the space complexity is $O(n\log n)$.

Segment tree

This section is documented in OI Wiki; see the link for details, as it is not expanded here.

The time complexity is $O(n) \sim O(\log n)$, and the space complexity is $O(n)$.

Four Russians

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

The improvement made by the Four Russians algorithm on top of an ST table is to divide the sequence into blocks.

More specifically, divide the original array, which we call array A, into blocks of $S$ elements each, for a total of $n/S$ blocks.

For each block, preprocess the minimum value among its elements, build an array B of length $n/S$, and preprocess B using an ST table.

At the same time, build an ST table for each partial block of array A.

When answering a query, we can split its interval into a contiguous interval of at most one block range in array B and contiguous intervals contained in at most two complete blocks of array A. These queries can clearly be answered by interval queries on ST tables.

When $S=\log n$, the preprocessing complexity is optimal, at $O((n / \log n)\log n+(n / \log n)\times\log n\times\log \log n)=O(n\log \log n)$.

The time complexity is $O(n\log \log n) \sim O(1)$, and the space complexity is $O(n\log \log n)$.

Of course, this implementation has a relatively large constant because each query needs to run three ST-table queries.

Plus/minus-one RMQ

If the difference between every pair of adjacent elements in a sequence is 1, RMQ on this sequence is called plus/minus-one RMQ. Using this property, the Four Russians algorithm can be improved to achieve time complexity $O(n) \sim O(1)$ and space complexity $O(n)$.

Since the bottleneck of the Four Russians algorithm is the within-block RMQ problem, we focus on optimizing the within-block RMQ problem.

Since the difference between adjacent numbers is $\pm 1$, after fixing the value at the left endpoint, the number of possible right-hand sequences of length at most $\log n$ is $\sum_{i=1}^{\log n} 2^{i-1}$, and this expression is clearly no greater than $n$.

This suggests that we can preprocess the value of minimum - first element for all cases, of which there are at most $n$.

During preprocessing, we need to preprocess the differences between adjacent numbers within the same block and represent them in binary.

When answering a query, find the binary representation corresponding to the query interval and look up the answer in the table.

This reduces the preprocessing time complexity of Four Russians to $O(n)$.

Cartesian trees in RMQ

If you are unfamiliar with Cartesian trees, please see Cartesian trees.

It is not difficult to see that the min/max between two points in the original sequence equals the weight of the LCA of the two points in the Cartesian tree. Therefore, we can use $O(n) \sim O(1)$ LCA queries between two points in a tree to solve RMQ. $O(n) \sim O(1)$ tree LCA is already described in LCA - standard RMQ, so it will not be expanded on here.

In summary, the application of Cartesian trees to RMQ transforms an ordinary RMQ problem into an LCA problem, and then into a plus/minus-one RMQ problem. Its time complexity is $O(n) \sim O(1)$. Of course, because there are many transformation steps, the constant factor of $O(n) \sim O(1)$ RMQ is relatively large.

If the data is random, we can also search the Cartesian tree by brute force. In this case, the expected time complexity is $O(n) \sim O(\log n)$, and the constant factor of this algorithm is often very small in practice.

Example Luogu P3865 Template ST Table

A linear RMQ algorithm based on bitmasking

Implicit requirements

• The sequence length $n$ satisfies $\log_2{n} \leq 64$.

Prerequisites

• Sparse Table

• Basic bit operations

• Prefix and suffix extrema

Algorithm principle

Divide the original sequence $A[1\cdots n]$ into blocks of length $O(\log_2{n})$, with $O(\frac{n}{\log_2{n}})$ blocks.

It is said that setting the block length to $1.5\times \log_2{n}$ gives a relatively small constant factor.

Record the maximum value of each block and maintain the maximum among blocks with an ST table, with complexity $O(n)$.

Record the maximum prefix and suffix value at every position in a block, $Pre[1\cdots n], Sub[1\cdots n]$ ($Pre[i]$ is the maximum value from $A[i]$ to the first position of the block containing it), with complexity $O(n)$.

If the queried $l,r$ lie in two different blocks, denoted as blocks $bl,br$, the maximum is the largest of the maximum among the blocks $[bl+1,br-1]$, $Sub[l]$, and $Pre[r]$.

The question now is what to do when $l,r$ lie in the same block.

Insert $A[1\cdots r]$ into a monotonic stack in order, recording indices and values, with values decreasing from the bottom of the stack to the top. Then the maximum in $A[l,r]$ is the first value found when scanning upward from the bottom of the stack whose index $p \geq l$.

Because $A[p]$ is the maximum in $A[l,r]$, when $A[p]$ is inserted, all of $A[l\cdots p-1]$ is popped, and while inserting $A[p+1\cdots r]$, $A[p]$ cannot be popped.

If we use $0/1$ to indicate whether each number is in the stack, we can use an integer bitmask; then $p$ is, after bit $l$, the position of the first $1$.

Because the block size is $O(\log_2{n})$, it is at most $64$ bits, so it can be stored in one integer (which is why the implicit condition is required).

#include <algorithm>
#include <cmath>
#include <cstdio>

constexpr int MAXN = 1e5 + 5;
constexpr int MAXM = 20;

struct RMQ {
  int N, A[MAXN];
  int blockSize;
  int S[MAXN][MAXM], Pow[MAXM], Log[MAXN];
  int Belong[MAXN], Pos[MAXN];
  int Pre[MAXN], Sub[MAXN];
  int F[MAXN];

  void buildST() {
    int cur = 0, id = 1;
    Pos[0] = -1;
    for (int i = 1; i <= N; ++i) {
      S[id][0] = std::max(S[id][0], A[i]);
      Belong[i] = id;
      if (Belong[i - 1] != Belong[i])
        Pos[i] = 0;
      else
        Pos[i] = Pos[i - 1] + 1;
      if (++cur == blockSize) {
        cur = 0;
        ++id;
      }
    }
    if (N % blockSize == 0) --id;
    Pow[0] = 1;
    for (int i = 1; i < MAXM; ++i) Pow[i] = Pow[i - 1] * 2;
    for (int i = 2; i <= id; ++i) Log[i] = Log[i / 2] + 1;
    for (int i = 1; i <= Log[id]; ++i) {
      for (int j = 1; j + Pow[i] - 1 <= id; ++j) {
        S[j][i] = std::max(S[j][i - 1], S[j + Pow[i - 1]][i - 1]);
      }
    }
  }

  void buildSubPre() {
    for (int i = 1; i <= N; ++i) {
      if (Belong[i] != Belong[i - 1])
        Pre[i] = A[i];
      else
        Pre[i] = std::max(Pre[i - 1], A[i]);
    }
    for (int i = N; i >= 1; --i) {
      if (Belong[i] != Belong[i + 1])
        Sub[i] = A[i];
      else
        Sub[i] = std::max(Sub[i + 1], A[i]);
    }
  }

  void buildBlock() {
    static int S[MAXN], top;
    for (int i = 1; i <= N; ++i) {
      if (Belong[i] != Belong[i - 1])
        top = 0;
      else
        F[i] = F[i - 1];
      while (top > 0 && A[S[top]] <= A[i]) F[i] &= ~(1 << Pos[S[top--]]);
      S[++top] = i;
      F[i] |= (1 << Pos[i]);
    }
  }

  void init() {
    for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
    blockSize = log2(N) * 1.5;
    buildST();
    buildSubPre();
    buildBlock();
  }

  int queryMax(int l, int r) {
    int bl = Belong[l], br = Belong[r];
    if (bl != br) {
      int ans1 = 0;
      if (br - bl > 1) {
        int p = Log[br - bl - 1];
        ans1 = std::max(S[bl + 1][p], S[br - Pow[p]][p]);
      }
      int ans2 = std::max(Sub[l], Pre[r]);
      return std::max(ans1, ans2);
    } else {
      return A[l + __builtin_ctz(F[r] >> Pos[l])];
    }
  }
} R;

int M;

int main() {
  scanf("%d%d", &R.N, &M);
  R.init();
  for (int i = 0, l, r; i < M; ++i) {
    scanf("%d%d", &l, &r);
    printf("%d\n", R.queryMax(l, r));
  }
  return 0;
}

Exercises

[BJOI 2020] Seal: SAM+RMQ