示例

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

int n, m;  //n个点，m次询问
struct node{
	int l, r;
	long long val;   
}a[400005];

void pushup(int rt){
	a[rt].val = min(a[rt << 1].val, a[rt << 1 | 1].val);
}
void build(int rt, int l, int r){
	a[rt].l = l, a[rt].r = r;
	if(l == r){
		cin >> a[rt].val;
		return;
	}
	int mid = l + r >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
	pushup(rt);
}
long long query(int rt, int l, int r){
	//当前结点被包含在[l, r]，直接返回
	if(l <= a[rt].l && a[rt].r <= r) return a[rt].val;
	int mid = a[rt].l + a[rt].r >> 1;
	long long ans = 1e18;
	if(l <= mid) ans = min(ans, query(rt << 1, l, r));
	if(r > mid) ans= min(ans, query(rt << 1 | 1, l, r));
	return ans;
}
int main(){
	cin >> n >> m;
	build(1, 1, n);   
	while(m--){
		int l, r;
		cin >> l >> r;
		cout << query(1, l, r) << ' ';
	}
	return 0;
}