• 线段树实现，PPT 上的写法

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

struct SegmentTree {
	int n;
	vector<int> t;
	
	SegmentTree(int n_) {
		n = n_;
		t.assign(2 * n, 0);
	}
	
	// 将原数组中 a[p] = v;
	void update(int p, int v) {
		p += n, t[p] = v;
		for (int i = p / 2; i >= 1; i /= 2) {
			t[i] = max(t[i * 2], t[i * 2 + 1]);
		}
	}
	
	// 查询原数组中 a[l] 到 a[r] 的最大值
	int query(int l, int r) {
		l += n, r += n;
		int ans = 0;
		while (l <= r) {
			if (l % 2 == 1) ans = max(ans, t[l]), l++;
			if (r % 2 == 0) ans = max(ans, t[r]), r--;
			l /= 2, r /= 2;
		}
		return ans;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n, q, x, p, l, r, cmd;
	
	cin >> n >> q;
	SegmentTree seg(n);
	for (int i = 0; i < n; i++) {
		cin >> x;
		seg.update(i, x);
	}
	
	while (q--) {
		cin >> cmd;
		if (cmd == 1) {
			cin >> p >> x;
			seg.update(p - 1, x);
		} else {
			cin >> l >> r;
			cout << seg.query(l - 1, r - 1) << '\n';
		}
	}
	return 0;
}