RMQ

簡介

RMQ 是英文 Range Maximum/Minimum Query 的縮寫，表示區間最大（最小）值。

在接下來的描述中，默認初始數組大小為 \(n\)，詢問次數為 \(m\)。

在接下來的描述中，默認時間複雜度標記方式為 \(O(A) \sim O(B)\)，其中 \(O(A)\) 表示預處理時間複雜度，而 \(O(B)\) 表示單次詢問的時間複雜度。

單調棧

由於 OI Wiki 中已有此部分的描述，本文僅給出鏈接。這部分不再展開。

時間複雜度 \(O(m\log m) \sim O(\log n)\)，空間複雜度 \(O(n)\)。

ST 表

由於 OI Wiki 中已有此部分的描述，本文僅給出鏈接。這部分不再展開。

時間複雜度 \(O(n\log n) \sim O(1)\)，空間複雜度 \(O(n\log n)\)。

線段樹

由於 OI Wiki 中已有此部分的描述，本文僅給出鏈接。這部分不再展開。

時間複雜度 \(O(n) \sim O(\log n)\)，空間複雜度 \(O(n)\)。

Four Russian

Four russian 是一個由四位俄羅斯籍的計算機科學家提出來的基於 ST 表的算法。

在 ST 表的基礎上 Four russian 算法對其做出的改進是序列分塊。

具體來説，我們將原數組——我們將其稱之為數組 A——每 \(S\) 個分成一塊，總共 \(n/S\) 塊。

對於每一塊我們預處理出來塊內元素的最小值，建立一個長度為 \(n/S\) 的數組 B，並對數組 B 採用 ST 表的方式預處理。

同時，我們對於數組 A 的每一個零散塊也建立一個 ST 表。

詢問的時候，我們可以將詢問區間劃分為不超過 1 個數組 B 上的連續塊區間和不超過 2 個數組 A 上的整塊內的連續區間。顯然這些問題我們通過 ST 表上的區間查詢解決。

在 \(S=\log n\) 時候，預處理複雜度達到最優，為 \(O((n / \log n)\log n+(n / \log n)\times\log n\times\log \log n)=O(n\log \log n)\)。

時間複雜度 \(O(n\log \log n) \sim O(1)\)，空間複雜度 \(O(n\log \log n)\)。

當然詢問由於要跑三個 ST 表，該實現方法的常數較大。

一些小小的算法改進

我們發現，在詢問的兩個端點在數組 A 中屬於不同的塊的時候，數組 A 中塊內的詢問是關於每一塊前綴或者後綴的詢問。

顯然這些詢問可以通過預處理答案在 \(O(n)\) 的時間複雜度內被解決。

這樣子我們只需要在詢問的時候進行至多一次 ST 表上的查詢操作了。

一些玄學的算法改進

由於 Four russian 算法以 ST 表為基礎，而算法競賽一般沒有非常高的時間複雜度要求，所以 Four russian 算法一般都可以被 ST 表代替，在算法競賽中並不實用。這裏提供一種在算法競賽中更加實用的 Four russian 改進算法。

我們將塊大小設為 \(\sqrt n\)，然後預處理出每一塊內前綴和後綴的 RMQ，再暴力預處理出任意連續的整塊之間的 RMQ，時間複雜度為 \(O(n)\)。

查詢時，對於左右端點不在同一塊內的詢問，我們可以直接 \(O(1)\) 得到左端點所在塊的後綴 RMQ，左端點和右端點之間的連續整塊 RMQ，和右端點所在塊的前綴 RMQ，答案即為三者之間的最值。

而對於左右端點在同一塊內的詢問，我們可以暴力求出兩點之間的 RMQ，時間複雜度為 \(O(\sqrt n)\)，但是單個詢問的左右端點在同一塊內的期望為 \(O(\frac{\sqrt n}{n})\)，所以這種方法的時間複雜度為期望 \(O(n)\)。

而在算法競賽中，我們並不用非常擔心出題人卡掉這種算法，因為我們可以通過在 \(\sqrt n\) 的基礎上隨機微調塊大小，很大程度上避免算法在根據特定塊大小構造的數據中出現最壞情況。並且如果出題人想要卡掉這種方法，則暴力有可能可以通過。

這是一種期望時間複雜度達到下界，並且代碼實現難度和算法常數均較小的算法，因此在算法競賽中比較實用。

以上做法參考了 P3793 由乃救爺爺中的題解。

加減 1RMQ

若序列滿足相鄰兩元素相差為 1，在這個序列上做 RMQ 可以成為加減 1RMQ，根究這個特性可以改進 Four Russian 算法，做到 \(O(n) \sim O(1)\) 的時間複雜度，\(O(n)\) 的空間複雜度。

由於 Four russian 算法的瓶頸在於塊內 RMQ 問題，我們重點去討論塊內 RMQ 問題的優化。

由於相鄰兩個數字的差值為 \(\pm 1\)，所以在固定左端點數字時長度不超過 \(\log n\) 的右側序列種類數為 \(\sum_{i=1}^{\log n} 2^{i-1}\)，而這個式子顯然不超過 \(n\)。

這啓示我們可以預處理所有不超過 \(n\) 種情況的最小值 - 第一個元素的值。

在預處理的時候我們需要去預處理同一塊內相鄰兩個數字之間的差，並且使用二進制將其表示出來。

在詢問的時候我們找到詢問區間對應的二進制表示，查表得出答案。

這樣子 Four russian 預處理的時間複雜度就被優化到了 \(O(n)\)。

笛卡爾樹在 RMQ 上的應用

不瞭解笛卡爾樹的朋友請移步笛卡爾樹。

不難發現，原序列上兩個點之間的 min/max，等於笛卡爾樹上兩個點的 LCA 的權值。根據這一點就可以藉助 \(O(n) \sim O(1)\) 求解樹上兩個點之間的 LCA 進而求解 RMQ。\(O(n) \sim O(1)\) 樹上 LCA 在 LCA - 標準 RMQ 已經有描述，這裏不再展開。

總結一下，笛卡爾樹在 RMQ 上的應用，就是通過將普通 RMQ 問題轉化為 LCA 問題，進而轉化為加減 1 RMQ 問題進行求解，時間複雜度為 \(O(n) \sim O(1)\)。當然由於轉化步數較多，\(O(n) \sim O(1)\) RMQ 常數較大。

如果數據隨機，還可以暴力在笛卡爾樹上查找。此時的時間複雜度為期望 \(O(n) \sim O(\log n)\)，並且實際使用時這種算法的常數往往很小。

例題 Luogu P3865【模板】ST 表

基於狀壓的線性 RMQ 算法

隱性要求

序列的長度 \(n\) 滿足 \(\log_2{n} \leq 64\)。

前置知識

Sparse Table
基本位運算
前後綴極值

算法原理

將原序列 \(A[1\cdots n]\) 分成每塊長度為 \(O(\log_2{n})\) 的 \(O(\frac{n}{\log_2{n}})\) 塊。

聽説令塊長為 \(1.5\times \log_2{n}\) 時常數較小。

記錄每塊的最大值，並用 ST 表維護塊間最大值，複雜度 \(O(n)\)。

記錄塊中每個位置的前、後綴最大值 \(Pre[1\cdots n], Sub[1\cdots n]\)（\(Pre[i]\) 即 \(A[i]\) 到其所在塊的塊首的最大值），複雜度 \(O(n)\)。

若查詢的 \(l,r\) 在兩個不同塊上，分別記為第 \(bl,br\) 塊，則最大值為 \([bl+1,br-1]\) 塊間的最大值，以及 \(Sub[l]\) 和 \(Pre[r]\) 這三個數的較大值。

現在的問題在於若 \(l,r\) 在同一塊中怎麼辦。

將 \(A[1\cdots r]\) 依次插入單調棧中，記錄下標和值，滿足值從棧底到棧頂遞減，則 \(A[l,r]\) 中的最大值為從棧底往上，單調棧中第一個滿足其下標 \(p \geq l\) 的值。

由於 \(A[p]\) 是 \(A[l,r]\) 中的最大值，因而在插入 \(A[p]\) 時，\(A[l\cdots p-1]\) 都被彈出，且在插入 \(A[p+1\cdots r]\) 時不可能將 \(A[p]\) 彈出。

而如果用 \(0/1\) 表示每個數是否在棧中，就可以用整數狀壓，則 \(p\) 為第 \(l\) 位後的第一個 \(1\) 的位置。

由於塊大小為 \(O(\log_2{n})\)，因而最多不超過 \(64\) 位，可以用一個整數存下（即隱性條件的原因）。

參考代碼

#include <bits/stdc++.h>

const int MAXN = 1e5 + 5;
const 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;
}

習題

[BJOI 2020] 封印：SAM+RMQ

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