Range Minimum Query
(segmentTree/rangeMin.hpp)

• View this file on GitHub
• Last update: 2022-07-06 23:37:31+09:00
• Include: #include "segmentTree/rangeMin.hpp"

• 半開半閉区間でクエリを処理することにすると扱いやすい
• 1-indexで木を構築すると実装しやすい
• クエリは0-index

Verified with

• test/segmentTree/rangeMin.aoj_DSL_2_A.test.cpp

Code

#pragma once
#include<vector>
#include<algorithm>
using namespace std;
class rangeMin {
 public:
  int size_ = 1;
  vector<long long> dat;

  void init(int sz) {
    while (size_ <= sz) size_ *= 2;
    dat.resize(size_ * 2, 1LL << 60);
  }
  void update(int pos, long long x) {
    pos += size_;
    dat[pos] = x;
    while (pos /= 2) {
      dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
    }
  }
  long long query_(int l, int r, int a, int b, int u) {
    if (l <= a && b <= r) return dat[u];
    if (r <= a || b <= l) return 1LL << 60;
    int mid = (a + b) / 2;
    long long v1 = query_(l, r, a, mid, u * 2);
    long long v2 = query_(l, r, mid, b, u * 2 + 1);
    return min(v1, v2);
  }
  long long query(int l, int r) { return query_(l, r, 0, size_, 1); }
};

#line 2 "segmentTree/rangeMin.hpp"
#include<vector>
#include<algorithm>
using namespace std;
class rangeMin {
 public:
  int size_ = 1;
  vector<long long> dat;

  void init(int sz) {
    while (size_ <= sz) size_ *= 2;
    dat.resize(size_ * 2, 1LL << 60);
  }
  void update(int pos, long long x) {
    pos += size_;
    dat[pos] = x;
    while (pos /= 2) {
      dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
    }
  }
  long long query_(int l, int r, int a, int b, int u) {
    if (l <= a && b <= r) return dat[u];
    if (r <= a || b <= l) return 1LL << 60;
    int mid = (a + b) / 2;
    long long v1 = query_(l, r, a, mid, u * 2);
    long long v2 = query_(l, r, mid, b, u * 2 + 1);
    return min(v1, v2);
  }
  long long query(int l, int r) { return query_(l, r, 0, size_, 1); }
};

Back to top page