Segment Tree (線段樹)

struct node {
	int v; node *l, *r;
	void pull() {v = max(l->v, r->v);}
	node(int _v = 0): v(_v), l(nullptr), r(nullptr) {}
} *root = new node;
void build(node*& o, int l, int r) { // [1, n]
	if (l == r) {
		cin >> o->v;
		return;
	}
	int m = (l + r) >> 1;
	o->l = new node, o->r = new node;
	build(o->l, l, m), build(o->r, m + 1, r);
	o->pull();
}
void upd(node* o, int l, int r, int x, int v) {
	if (l == r) {
		o->v = v;
		return;
	}
	int m = (l + r) >> 1;
	if (x <= m) upd(o->l, l, m, x, v);
	else upd(o->r, m + 1, r, x, v);
	o->pull();
}
int qry(node* o, int l, int r, int ql, int qr) { // [ql, qr]
	if (ql <= l && r <= qr) return o->v;
	int m = (l + r) >> 1, ret = -1e9;
	if (ql <= m) ret = max(ret, qry(o->l, l, m, ql, qr));
	if (qr > m) ret = max(ret, qry(o->r, m + 1, r, ql, qr));
	return ret;
}

#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
constexpr int N = 2e5 + 1;
int seg[N << 2];
void build(int id, int l,int r) { // [1, n]
	if (l == r) {
		cin >> seg[id];
		return;
	}
	int m = (l + r) >> 1;
	build(lc(id), l, m);
	build(rc(id), m + 1, r);
	seg[id] = max(seg[lc(id)], seg[rc(id)]);
}
void upd(int id, int l, int r, int x, int v) {
	if (l == r) {
		seg[id] = v;
		return;
	}
	int m = (l + r) >> 1;
	if (x <= m) upd(lc(id), l, m, x, v);
	else upd(rc(id), m + 1, r, x, v);
	seg[id] = max(seg[lc(id)], seg[rc(id)]);
}
int qry(int id, int l, int r, int ql, int qr) { // [ql, qr]
	if (ql <= l && r <= qr) return seg[id];
	if (ql > r || qr < l) return 0;
	int m = (l + r) >> 1;
	return max(qry(lc(id), l, m, ql, qr), qry(rc(id), m + 1, r, ql, qr));
}

#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
constexpr int N = 2e5 + 1;
int seg[N << 1], n;
void upd(int x, int v) {
	for (seg[x += n] = v; x > 1; x >>= 1)
		seg[x >> 1] = max(seg[x], seg[x ^ 1]);
}
int qry(int l, int r) { // [ql, qr)
	int ret = -1e9;
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) ret = max(ret, seg[l++]);
		if (r & 1) ret = max(ret, seg[--r]);
	}
	return ret;
}
void build() { // [0, n)
	for (int i = 0; i < n; i++)
		cin >> seg[i + n];
	for (int i = n - 1; i; i--)
		seg[i] = max(seg[lc(i)], seg[rc(i)]);
}