Dynamic Range Minimum Queries

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
 
int tree_min(vector<int> &tree, int a, int b) {
  a += n;
  b += n;
  int m = 1e9+5;
 
  while (a <= b) {
    if ((a % 2) == 1) {
      m = min(m, tree[a]);
      a++;
    }
    if ((b % 2) == 0) {
      m = min(m, tree[b]);
      b--;
    }
    a /= 2;
    b /= 2;
  }
  return m;
}
 
void update(vector<int> &tree, int i, int v) {
  i += n;
  tree[i] = v;
  int newMin;
  while (i > 1) {
    i /= 2;
    newMin = min(tree[2 * i], tree[2 * i + 1]);
    if (tree[i] != newMin) {
      tree[i] = newMin;
    } else
      return;
  }
}
 
int main() {
  // ios::sync_with_stdio(false);
  // cin.tie(0);
  int q;
  cin >> n >> q;
 
  auto values = vector<int>(n);
 
  for (int i = 0; i < n; i++) {
    cin >> values[i];
  }
 
  int tree_size = 2 * n;
 
  auto tree = vector<int>(tree_size, 1e9+5);
 
  for (int i = n; i < tree_size; i++) {
    tree[i] = values[i - n];
  }
 
  for (int i = n - 1; i > 0; i--) {
    tree[i] = min(tree[2 * i], tree[2 * i + 1]);
  }
 
  for (int i = 0; i < q; i++) {
    int type, a, b;
    cin >> type >> a >> b;
    if (type == 1) {
      // update value at a to b
      update(tree, a - 1, b);
    } else {
      // query [a,b]
      cout << tree_min(tree, a - 1, b - 1) << endl;
    }
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED