Shared code

#include <bits/stdc++.h>
using namespace std;

#define LSB(x) ((x) & -(x))

template <class T>
struct BIT {
  using F = function<T(const T&, const T&)>;
  
  const vector<T>& a;
  const T nil;
  const F f;
  const int n;
  vector<T> b1, b2;
  
  void chf(T& lhs, const T& rhs) {
    lhs = f(lhs, rhs);
  }
  
  BIT(const vector<T>& a_, const T& nil_, const F& f_) : a(a_), nil(nil_), f(f_), n(int(a.size()) - 1), b1(n + 1, nil), b2(n + 1, nil) {
    for (int i = 1; i <= n; ++i) {
      b1[i] = b2[i] = a[i];
    }
    for (int i = 1; i <= n; ++i) {
      if (i + LSB(i) <= n) {
        chf(b1[i + LSB(i)], b1[i]);
      }
    }
    for (int i = n; i >= 1; --i) {
      if (i - LSB(i) >= 1) {
        chf(b2[i - LSB(i)], b2[i]);
      }
    }
  }
  
  T query(int L, int R) {
    if (L > R) return nil;
    T res = nil;
    int i;
    for (i = L; i + LSB(i) <= R; i += LSB(i)) {
      chf(res, b2[i]);
    }
    for (i = R; i - LSB(i) >= L; i -= LSB(i)) {
      chf(res, b1[i]);
    }
    return f(res, a[i]);
  }
  
  void update(int p, const T& v) {
    b1[p] = b2[p] = v;
    for (int i = p - 1; i >= 1 && i > p - LSB(p); i -= LSB(i)) {
      chf(b1[p], b1[i]);
    }
    for (int i = p + 1; i <= n && p <= i - LSB(i); i += LSB(i)) {
      chf(b2[p], b2[i]);
    }
    T cur = nil;
    for (int i = p, j = p - 1; i <= n; i += LSB(i)) {
      for (; j >= 1 && j > i - LSB(i); j -= LSB(j)) {
        chf(cur, b1[j]);
      }
      b1[i] = f(cur, a[i]);
      chf(cur, b2[i]);
    }
    cur = nil;
    for (int i = p, j = p + 1; i >= 1; i -= LSB(i)) {
      for (; j <= n && i <= j - LSB(j); j += LSB(j)) {
        chf(cur, b2[j]);
      }
      b2[i] = f(cur, a[i]);
      chf(cur, b1[i]);
    }
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  vector<int> x(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> x[i];
  }
  BIT<int> bit(x, INT_MAX, [&](int lhs, int rhs) { return min(lhs, rhs); });
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int k, u;
      cin >> k >> u;
      x[k] = u;
      bit.update(k, u);
    } else {
      int a, b;
      cin >> a >> b;
      cout << bit.query(a, b) << "\n";
    }
  }
  return 0;
}