Range Minimum Query (RMQ)

概要

以下のクエリが処理できるセグメント木の実装

  • \(a_i\) の値を \(x\) に更新

  • \(a_l, a_{l+1}, ..., a_{r-1}\) の最小値を求める

セグメント木の最も基本的な形。

計算量

  • 更新: \(O(\log N)\)

  • 区間最小値: \(O(\log N)\)

実装(再起版)

#include<algorithm>
using namespace std;
using ll = long long;

#define N 100007
 
class SegmentTree {
  const static ll inf = (1LL << 31) - 1;
  int n, n0;
  ll data[4*N];
 
public:
  SegmentTree(int n) {
    n0 = 1;
    while(n0 < n) n0 <<= 1;
    for(int i=0; i<2*n0; ++i) data[i] = inf;
  }
 
  void update(int k, ll x) {
    k += n0-1;
    data[k] = x;
    while(k > 0) {
      k = (k - 1) / 2;
      data[k] = min(data[2*k+1], data[2*k+2]);
    }
  }
 
  ll __query(int a, int b, int k, int l, int r) {
    if(a <= l && r <= b) {
      return data[k];
    }
    if(r <= a || b <= l) {
      return inf;
    }
    ll lv = __query(a, b, 2*k+1, l, (l+r)/2);
    ll rv = __query(a, b, 2*k+2, (l+r)/2, r);
    return min(lv, rv);
  }
 
  ll query(int a, int b) {
    return __query(a, b, 0, 0, n0);
  }
};

Verified

  • AOJ: "DSL_2_A: Range Query - Range Minimum Query (RMQ)": source (C++14, 0.11sec)

実装(非再帰版)

#include<algorithm>
using namespace std;
using ll = long long;

#define N 100007
 
class SegmentTree {
  const static ll inf = (1LL << 31) - 1;
  int n, n0;
  ll data[4*N];
 
public:
  SegmentTree(int n) {
    n0 = 1;
    while(n0 < n) n0 <<= 1;
    for(int i=0; i<2*n0; ++i) data[i] = inf;
  }
 
  void update(int k, ll x) {
    k += n0-1;
    data[k] = x;
    while(k > 0) {
      k = (k - 1) / 2;
      data[k] = min(data[2*k+1], data[2*k+2]);
    }
  }
 
  ll query(int l, int r) {
    int l0 = l + n0, r0 = r + n0;
    ll s = inf;
    while(l0 < r0) {
      if(r0 & 1) {
        --r0;
        s = min(s, data[r0-1]);
      }
      if(l0 & 1) {
        s = min(s, data[l0-1]);
        ++l0;
      }
      l0 >>= 1; r0 >>= 1;
    }
    return s;
  }
};

Verified

  • AOJ: "DSL_2_A: Range Query - Range Minimum Query (RMQ)": source (C++14, 0.12sec)

戻る