问题描述

RMQ (Range Minimum/Maximum Query)问题是指：
对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。

例题

AcWing 1273. 天才的记忆 RMQ
AcWing 1270. 数列区间最大值 RMQ
AcWing 1272. 与众不同 双指针 + RMQ + 二分

方法1 线段树

很简单，不赘述了

  1. static class Node {
  2.         int l, r;
  3.         int max;
  4.         Node(int l, int r) {
  5.             this.l = l;
  6.             this.r = r;
  7.         }
  8.     }
  9.     static int N = 200010;
  10.     static Node[] tr = new Node[N * 4];
  11.     static int n;
  12.     static int[] a = new int[N];
  13.     static void solve() {
  14.         n = ni();
  15.         for (int i = 1; i <= n; i++)
  16.             a[i] = ni();
  17.         build(1, 1, n);
  18.         int m = ni();
  19.         while (m-- > 0) {
  20.             int l = ni(), r = ni();
  21.             out.println(query(1, l, r));
  22.         }
  23.     }
  25.     static void build(int u, int l, int r) {
  26.         if (l == r) {
  27.             tr[u] = new Node(l, r);
  28.             tr[u].max = a[l];
  29.         } else {
  30.             int mid = l + r >> 1;
  31.             tr[u] = new Node(l, r);
  32.             build(u << 1 , l, mid);
  33.             build(u << 1 | 1, mid + 1, r);
  34.             pushup(u);
  35.         }
  36.     }
  38.     static int query(int u, int l, int r) {
  39.         if (l <= tr[u].l && r >= tr[u].r)
  40.             return tr[u].max;
  41.         else {
  42.             int mid = tr[u].l + tr[u].r >> 1;
  43.             int res = Integer.MIN_VALUE;
  44.             if (l <= mid) res = Math.max(res, query(u << 1, l, r));
  45.             if (r > mid) res = Math.max(res, query(u << 1 | 1, l, r));
  46.             return res;
  47.         }   
  48.     }
  50.     static void pushup(int u) {
  51.         tr[u].max = Math.max(tr[u << 1].max, tr[u << 1 | 1].max);
  52.     }

方法2 Fenwick Tree

使用树状数组求解区间最值，时间复杂度为O(log2n)
思想：
tr[i]维护[i - lowbit[i] + 1, i]这一段区间的最值

  1. static final int N = 200010;
  2. static int[] tr = new int[N];
  3. static int[] a = new int[N];
  4. static int n;
  5. static void solve() {
  6.     n = ni();
  7.     for (int i = 1; i <= n; i++) {
  8.         a[i] = ni();
  9.         // modify(i, a[i]);
  10.     }
  11.     build();
  13.     int m = ni();
  14.     while (m-- > 0) {
  15.         int l = ni(), r = ni();
  16.         out.println(query(l, r));
  17.     }
  18. }
  20. static void build() {
  21.     for (int i = 1; i <= n; i++) {
  22.         tr[i] = a[i];
  23.         for (int j = 1; j < lowbit(i); j <<= 1)
  24.             tr[i] = Math.max(tr[i], tr[i - j]);
  25.     }
  26. }
  28. static int query(int l, int r) {
  29.     if (l == r)
  30.         return a[l];
  31.     if (l == r - lowbit(r) + 1)
  32.         return tr[r];
  33.     else if (l < r - lowbit(r) + 1)
  34.         return Math.max(tr[r], query(l, r - lowbit(r)));
  35.     else
  36.         return Math.max(a[r], query(l, r - 1));
  37. }
  39. static int lowbit(int x) {
  40.     return x & (-x);
  41. }
  42. static void modify(int idx, int x) {
  43.         a[idx] = x;
  44.         for (int i = idx; i <= n; i += lowbit(i)) {
  45.             if (x >= tr[i])
  46.                 tr[i] = x;
  47.             else {
  48.                 tr[i] = x;
  49.                 for (int j = 1; j < lowbot(i); j <<= 1)
  50.                     tr[i] = Math.max(tr[i], tr[i - j]);
  51.             }
  52.         }
  53.     }
  54. }