Segment tree

struct Segt {
  using T = int;

  static constexpr T def = 1<<30;
  int cap; vector<T> seg;

  Segt(int c = 0, T d = def) : seg(2*(c+1), d), cap(c+1) {}

  T segfun(T i, T j) { return min(i, j); }
  void update(int i, T v) {
    for (seg[i += cap] = v; i >>= 1; ) {
      seg[i] = segfun(seg[i<<1], seg[(i<<1)^1]);
    }
  }
  T ask(int l, int r) {
    T r1 = def, r2 = def;
    for (l += cap, r += cap; l <= r; l >>= 1, r >>= 1) {
      if (l&1) r1 = segfun(r1, seg[l++]);
      if (~r&1) r2 = segfun(r2, seg[r--]);
    }
    return segfun(r1, r2);
  }
};

 

ask(l, r) 구간 [l, r] 에 대한 segfun 연산 수행결과를 반환

 

KACTL를 많이 참고하였다