Dynamic Range Minimum Queries

#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>

using namespace std;

// Point update + range minimum via an iterative bottom-up segment tree (O(log n) per query).
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  if (!(cin >> n >> q)) return 0;

  vector<int> t(2 * n);
  for (int i = 0; i < n; i++) cin >> t[n + i];
  for (int i = n - 1; i > 0; i--) t[i] = min(t[2 * i], t[2 * i + 1]);

  for (int i = 0; i < q; i++) {
    int type, a, b;
    cin >> type >> a >> b;
    if (type == 1) {
      int p = n + a - 1;
      t[p] = b;
      for (p >>= 1; p > 0; p >>= 1) t[p] = min(t[2 * p], t[2 * p + 1]);
    } else {
      int res = numeric_limits<int>::max();
      for (int l = n + a - 1, r = n + b; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = min(res, t[l++]);
        if (r & 1) res = min(res, t[--r]);
      }
      cout << res << '\n';
    }
  }
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED