RMQ

Introduction

RMQ stands for Range Maximum/Minimum Query, which refers to finding the maximum (or minimum) value within a given interval.

In the following descriptions, the default initial array size is \(n\), and the number of queries is \(m\).

In the following descriptions, the default time complexity notation is \(O(A) \sim O(B)\), where \(O(A)\) represents the preprocessing time complexity, and \(O(B)\) represents the time complexity for a single query.

Monotonic Stack

Since this part is already described in OI Wiki, this article only provides a link. It will not be elaborated further here.

Time complexity: \(O(m\log m) \sim O(\log n)\), space complexity: \(O(n)\).

Sparse Table (ST Table)

Since this part is already described in OI Wiki, this article only provides a link. It will not be elaborated further here.

Time complexity: \(O(n\log n) \sim O(1)\), space complexity: \(O(n\log n)\).

Segment Tree

Since this part is already described in OI Wiki, this article only provides a link. It will not be elaborated further here.

Time complexity: \(O(n) \sim O(\log n)\), space complexity: \(O(n)\).

Four Russian

Four Russian is an algorithm based on the Sparse Table, proposed by four Russian computer scientists.

The improvement made by the Four Russian algorithm over the Sparse Table is sequence blocking.

Specifically, we divide the original array—referred to as array A—into blocks of size \(S\), resulting in \(n/S\) blocks in total.

For each block, we precompute the minimum value of the elements within the block, creating an array B of length \(n/S\), and preprocess array B using the Sparse Table method.

Additionally, we build a Sparse Table for each scattered block of array A.

When answering a query, we can divide the query interval into at most one contiguous block interval on array B and at most two contiguous intervals within whole blocks of array A. Clearly, these subproblems can be solved using interval queries on the Sparse Tables.

When \(S=\log n\), the preprocessing complexity reaches its optimal value: \(O((n / \log n)\log n+(n / \log n)\times\log n\times\log \log n)=O(n\log \log n)\).

Time complexity: \(O(n\log \log n) \sim O(1)\), space complexity: \(O(n\log \log n)\).

However, since queries require running three Sparse Table queries, the constant factor of this implementation is relatively large.

Some Minor Algorithm Improvements

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

Clearly, these queries can be solved in \(O(n)\) time complexity by preprocessing the answers.

This way, we only need to perform at most one Sparse Table query operation per query.

Some Mysterious Algorithm Improvements

Since the Four Russian algorithm is based on the Sparse Table, and algorithm competitions generally do not have very high time complexity requirements, the Four Russian algorithm can usually be replaced by the Sparse Table and is not very practical in algorithm competitions. Here, we provide a more practical improved version of the Four Russian algorithm for algorithm competitions.

We set the block size to \(\sqrt n\), then precompute the RMQ for prefixes and suffixes within each block, and brute-force precompute the RMQ for any consecutive whole blocks, with a time complexity of \(O(n)\).

When querying, for queries where the left and right endpoints are not in the same block, we can directly obtain the suffix RMQ of the block containing the left endpoint, the RMQ of the consecutive whole blocks between the left and right endpoints, and the prefix RMQ of the block containing the right endpoint in \(O(1)\) time. The answer is the maximum/minimum among these three values.

For queries where the left and right endpoints are in the same block, we can brute-force compute the RMQ between the two points, with a time complexity of \(O(\sqrt n)\). However, the probability that the two endpoints of a single query are in the same block is \(O(\frac{\sqrt n}{n})\), so the expected time complexity of this method is \(O(n)\).

In algorithm competitions, we do not need to worry too much about problem setters trying to break this algorithm, because we can randomly adjust the block size around \(\sqrt n\) to largely avoid worst-case scenarios on data specifically constructed for a particular block size. Moreover, if a problem setter tries to break this method, brute-force might still pass.

This is an algorithm with expected time complexity reaching the lower bound, relatively simple implementation, and small constant factors, making it quite practical in algorithm competitions.

The above approach references the solution in P3793 You Nai Saves Grandpa.

±1 RMQ

If the sequence satisfies the condition that adjacent elements differ by 1, performing RMQ on this sequence can be called ±1 RMQ. Leveraging this property, the Four Russian algorithm can be improved to achieve \(O(n) \sim O(1)\) time complexity and \(O(n)\) space complexity.

Since the bottleneck of the Four Russian algorithm lies in the RMQ problem within blocks, we focus on optimizing the intra-block RMQ problem.

Because the difference between adjacent numbers is \(\pm 1\), for a fixed left endpoint number, the number of possible right-side sequences of length at most \(\log n\) is \(\sum_{i=1}^{\log n} 2^{i-1}\), which clearly does not exceed \(n\).

This suggests that we can precompute the values of minimum - first element for all possible cases not exceeding \(n\).

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

During a query, we find the binary representation corresponding to the query interval and look up the answer in the precomputed table.

This way, the preprocessing time complexity of the Four Russian algorithm is optimized to \(O(n)\).

Application of Cartesian Tree in RMQ

For those unfamiliar with Cartesian trees, please refer to Cartesian Tree.

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. Based on this, we can solve RMQ by converting it to finding the LCA of two points on the tree using \(O(n) \sim O(1)\) LCA queries. The \(O(n) \sim O(1)\) tree LCA method is already described in LCA - Standard RMQ and will not be elaborated here.

In summary, the application of Cartesian trees in RMQ involves transforming the general RMQ problem into an LCA problem, which is then converted into a ±1 RMQ problem for solving, with a time complexity of \(O(n) \sim O(1)\). However, due to the multiple transformation steps, the constant factor for \(O(n) \sim O(1)\) RMQ is relatively large.

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

Example Problem Luogu P3865【Template】Sparse Table

Bitmask-Based Linear RMQ Algorithm

Implicit Requirement

The length \(n\) of the sequence satisfies \(\log_2{n} \leq 64\).

Prerequisites

Sparse Table
Basic bit operations
Prefix and suffix extremum

Algorithm Principle

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

It is said that setting the block length to \(1.5\times \log_2{n}\) often results in smaller constant factors.

Record the maximum value of each block and use a Sparse Table to maintain the maximum values between blocks. Complexity: \(O(n)\).

Record the prefix and suffix maximum values for each position within a block: \(Pre[1\cdots n], Sub[1\cdots n]\) (where \(Pre[i]\) is the maximum value from \(A[i]\) to the start of its block). Complexity: \(O(n)\).

If the query \(l,r\) lies in two different blocks, denoted as blocks \(bl\) and \(br\), then the maximum value is the maximum among: the maximum value of blocks \([bl+1,br-1]\), \(Sub[l]\), and \(Pre[r]\).

Now, the problem is what to do if \(l,r\) are in the same block.

Insert \(A[1\cdots r]\) into a monotonic stack in order, recording indices and values, ensuring the values decrease from the bottom to the top of the stack. Then, the maximum value in \(A[l,r]\) is the value in the monotonic stack (from bottom to top) whose index \(p\) is the first satisfying \(p \geq l\).

Since \(A[p]\) is the maximum in \(A[l,r]\), when inserting \(A[p]\), all elements \(A[l\cdots p-1]\) are popped, and when 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 for bitmask representation. Then, \(p\) is the position of the first \(1\) after the \(l\)-th bit.

Since the block size is \(O(\log_2{n})\), it requires at most \(64\) bits, which can be stored in an integer (hence the implicit requirement).

Reference Code

#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

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用