Dynamic Range Minimum Queries

#include <iostream>
#include <cstring>
 
using namespace std;

const int N = 2e5 + 5;

struct segment_tree {
  int st[4 * N];

  segment_tree() {
    memset(st, 0x3f, sizeof(st));
  }

  void upd(int id, int tl, int tr, int k, int u) {
    if (tl == tr) {
      st[id] = u;
      return;
    }
    int tm = (tl + tr) >> 1;
    if (k <= tm) {
      upd(id << 1, tl, tm, k, u);
    } else if (tm + 1 <= k) {
      upd(id << 1 | 1, tm + 1, tr, k, u);
    }
    st[id] = min(st[id << 1], st[id << 1 | 1]);
  }

  int get(int id, int tl, int tr, int l, int r) {
    if (l <= tl && tr <= r) {
      return st[id];
    }
    int tm = (tl + tr) >> 1;
    if (r <= tm) {
      return get(id << 1, tl, tm, l, r);
    } else if (tm + 1 <= l) {
      return get(id << 1 | 1 , tm + 1, tr, l, r);
    } else {
      return min(get(id << 1, tl, tm, l, r), get(id << 1 | 1, tm + 1, tr, l, r));
    }
  }
};

int n, q;
int x[N];
segment_tree st;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> x[i];
    st.upd(1, 1, n, i, x[i]);
  }
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int k, u;
      cin >> k >> u;
      st.upd(1, 1, n, k, u);
    } else if (t == 2) {
      int a, b;
      cin >> a >> b;
      cout << st.get(1, 1, n, a, b) << '\n';
    }
  }
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED