Segment Tree RMQ.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

#define MAXN 100005
int n, q, i, j, c;
int a[MAXN];
int t[MAXN * 4];

void build(int node, int st, int en) {
  if (st == en) {
    t[node] = a[st];
    return;
  }
  build(node * 2, st, (st + en) / 2);
  build(node * 2 + 1, (st + en) / 2 + 1, en);
  t[node] = max(t[node * 2], t[node * 2 + 1]);
}

int query(int node, int st, int en, int i, int j) {
  if (st > j || en < i) return -1e9;
  if (st >= i && en <= j) return t[node];
  int a = query(node * 2, st, (st + en) / 2, i, j);
  int b = query(node * 2 + 1, (st + en) / 2 + 1, en, i, j);
  return max(a, b);
}

void update(int node, int st, int en, int x, int v) {
  if (st > x || en < x) return;
  if (st == en) {
    t[node] = v;
    return;
  }
  update(node * 2, st, (st + en) / 2, x, v);
  update(node * 2 + 1, (st + en) / 2 + 1, en, x, v);
  t[node] = max(t[node * 2], t[node * 2 + 1]);
}

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];
  build(1, 0, n - 1);
  cin >> q;
  while (q--) {
    cin >> c >> i >> j;
    if (c)
      cout << query(1, 0, n - 1, i, j) << "\n";
    else
      update(1, 0, n - 1, i, j);
  }
  return 0;
}