C++老管家的忠诚（线段树做法）

区间查询，果断想到线段树，看了一下题解有很多用的st表，但感觉st表模板太难记了，线段树相对好记很多，还是线段树更香一点。

树状数组也可以求最值但得改模板。

参考代码:

#include using namespace std;

const int N = 100010;
int w[N];
int n, m;
struct node {
	int l, r;
	int minv;
}tr[N * 4];

//向上更新
void pushup(int u) {
	tr[u].minv = min(tr[u << 1].minv, tr[u << 1 | 1].minv);
}

//初始化
void bulid(int u, int l, int r) {
	if (l == r) tr[u]= { l,r,w[r] };
	else {
		tr[u] = { l,r };
		int mid = l + r >> 1;
		bulid(u << 1, l, mid);
		bulid(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
}

//区间查询
int query(int u, int l, int r) {
	if (tr[u].l >= l && tr[u].r > 1;
	if (l <= mid) res = min(res, query(u << 1, l, r));
	if (r > mid)res = min(res, query(u << 1 | 1, l, r));
	return res;
}

//将x位置的数修改为v,此题没有用到单点修改，这个函数可以不写
void modify(int u, int x, int v) {
	if (tr[u].l == tr[u].r) tr[u].minv = v;
	else {
		int mid = tr[u].l + tr[u].r >> 1;
		if (x <= mid)modify(u << 1, x, v);
		else modify(u << 1 | 1, x, v);
		pushup(u);
	}
}
int main()
{
        //大输入记得开取消同步流或者用cstdio不然必超时
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> m >> n;
	for (int i = 1; i > w[i];
	bulid(1, 1, m);
	while (n--) {
		int l, r;
		cin >> l >> r;
		cout << query(1, l, r) << '\n';
	}
	return 0;
}