• 线段树实现，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;
}

• 线段树实现
• 单点更新复杂度：$O(log(n))$
• 区间最值复杂度：$O(log(n))$
• 实现简单，扩展性强，推荐！！
• 这里是用位操作优化后的简洁写法，如果不是很明白，可以参考老师 PPT 上的写法

// 参考资料
// https://www.luogu.com.cn/article/pfhvnr5i

// hdu1754
// https://acm.hdu.edu.cn/viewcode.php?rid=40390862
// 468ms

// LS1227
// https://www.gzlzoi.cn/d/lzoi2025/record/68c37971e1b585b55d44fd25
// 54ms

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

const int inf = numeric_limits<int>::max() / 2;

struct SegmentTree {
	int n;
	vector<int> t;
	
	SegmentTree(int n_) {
		n = n_;
		t.assign(2 * n, 0);  // 注意不同的问题, 初值不一样!!
	}
	
	void update(int p, int v) {
		for (t[p += n] = v; p >>= 1; ) t[p] = max(t[p << 1], t[p << 1 | 1]);
		
//	    相当于下面 4 句话
//		p += n;     // 找到原数组的 a[p] 在线段树中对应的位置
//		t[p] += v;  // 把线段树中的节点 +v
//		p /= 2;     // 找到 p 的上层节点
//		while (p > 0) t[p] = max(t[p * 2], t[p * 2 + 1]), p /= 2;  //合并节点的值
	}
	
	int query(int l, int r) {
		int ans = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1){
			if (l & 1) ans = max(ans, t[l++]);
			if (r & 1) ans = max(ans, t[--r]);
		}
		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) << '\n';
		}
	}
	return 0;
}

• 树状数组实现
• 单点更新复杂度：$O(log(n) \times log(n))$，不算优秀
• 区间最值复杂度：$O(log(n))$
• 这个写法虽然写起来简单，但时间复杂度不如线段树优秀，大家了解就好

// 参考资料
// https://oi-wiki.org/ds/fenwick/
// https://www.cnblogs.com/ambition/archive/2011/04/06/bit_rmq.html

// hdu 1754
// https://acm.hdu.edu.cn/viewcode.php?rid=40390236
// 873ms

// LS1227
// https://www.gzlzoi.cn/d/lzoi2025/record/68c37804e1b585b55d44fcf6
// 67ms

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

const int inf = numeric_limits<int>::max() / 2;

template <typename T>  // 使用 template 模板, 用法见定义
struct Fenwick {
	int n;
	vector<T> a, o;  // a: 树状数组, o: 原数组
	
	Fenwick(int n_) : n(n_) {
		// 注意: 树状数组都是从 1 开始编号 a[1..n], 不要从 0 开始
		// 相当于 a = vector<int>(n + 1, 0)
		a.assign(n + 1, 0);  // 树状数组
		
		o.assign(n + 1, 0);  // 原数组
	}
	
	// 将原数组的第 p 个数修改为 v, o[p] = v
	// O(log(n) ^2)
	void update(int p, T v) {
		
		o[p] = v;  // 先修改原数组
		
		// 所有包含 o[p] 的都要更新
		for (; p <= n; p += p & -p) {
			a[p] = o[p];  
			int l = p - (p & -p) + 1, r = p - 1;
			while (l <= r) {
				int d = r & -r;
				if (r - d + 1 >= l) a[p] = max(a[p], a[r]), r -= d;
				else a[p] = max(a[p], o[r]), r--;
			}
		}
	}
	
	// 求 [l, r] 区间最值
	// O(log(n))
	T query(int l, int r) {
		T ans = 0;
		while (l <= r) {
			int d = r & -r;
			if (r - d + 1 >= l) ans = max(ans, a[r]), r -= d;
			else ans = max(ans, o[r]), r--;
		}
		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;
	
	Fenwick<int> f(n);
	for (int i = 1; i <= n; i++) {
		cin >> x;
		f.update(i, x);
	}
	
	while (q--) {
		cin >> cmd;
		if (cmd == 1) {
			cin >> p >> x;
			f.update(p, x);
		} else {
			cin >> l >> r;
			cout << f.query(l, r) << '\n';
		}
	}
	return 0;
}