静态开点版本

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, inf = INT_MAX;
#define int long long
#define lc(p) (p << 1)      /*i的左孩子编号为i*2*/
#define rc(p) (p << 1 | 1)  /*i的右孩子编号为i*2+1*/
int a[N];/*记录数组初值*/
struct node
{int l/*左区间*/, r/*右区间*/, v/*区间最小值*/;}tr[N << 2]/*开四倍, 防炸*/;
void pushup(int p){tr[p].v = min(tr[lc(p)].v, tr[rc(p)].v);}/*更新节点权值*/
void build(int p, int l, int r)/*节点p管理区间[l,r]构造线段树*/
{
    tr[p] = {l, r, inf};/*赋值节点p*/
    if (l == r)/*如果只管理一个点*/
        {tr[p].v = a[l];/*直接赋值权值*/ return;/*已经到最低层了*/ }
    int mid = (l + r) >> 1;
    build(lc(p), l, mid);/*左孩子管理p管理范围的左半边*/
    build(rc(p), mid + 1, r);/*右孩子管理剩下右半边*/
    pushup(p);/*递归回来时更新p的区间和*/
}
int query(int p, int l, int r)/*查询区间[l,r]的区间最小值*/
{
    if (r < tr[p].l or tr[p].r < l)/*如果p管理区间与[l,r]无关*/
        return inf;/*对答案无贡献*/
    if (l <= tr[p].l and tr[p].r <= r)/*p区间在区间[l,r]内*/
        return tr[p].v;/*不会贡献区间以外的答案, 直接返回p的权值*/

    /*如果p包括了查询区间以外的值, 就将区间细分到左右儿子再统计*/
    return min(query(lc(p), l, r), query(rc(p), l, r));
}
signed main()
{
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--)
    {
        int l, r; cin >> l >> r; l ++;
        cout << query(1, l, r) << '\n';
    }
    return 0;
}

动态开点版本

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, inf = INT_MAX;
#define int long long
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
int a[N];
struct node{int ls, rs, v;} tr[N << 2];
void pushup(int p){tr[p].v = min(tr[lc(p)].v, tr[rc(p)].v);}

int tot = 0;
int newnode()
{
    tot ++; lc(tot) = rc(tot) = 0;
    tr[tot].v = inf;
    return tot;
}

void build(int &p, int l, int r)
{
    if (!p) p = newnode();
    if (l == r) {tr[p].v = a[l]; return;}
    int mid = (l + r) >> 1;
    build(lc(p), l, mid);
    build(rc(p), mid + 1, r);
    pushup(p);
}
int query(int p, int l, int r, int ql, int qr)
{
    if (!p) return inf;
    if (qr < l || r < ql) return inf;
    if (ql <= l && r <= qr) return tr[p].v;

    int mid = (l + r) >> 1;
    return min(query(lc(p), l, mid, ql, qr),
               query(rc(p), mid + 1, r, ql, qr));
}

signed main()
{
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int root = 0;
    build(root, 1, n);
    while (q--)
	{
        int l, r; cin >> l >> r; l++;
		cout << query(root, 1, n, l, r) << '\n';
    }
    return 0;
}

阎帝的代码

#include<bits/stdc++.h>
#define LL long long
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
using namespace std;
const int N=5e5+10;
struct node{int l,r,mi;}t[N<<2];
int a[N],n,q;
void pu(int p){t[p].mi=min(t[lc(p)].mi,t[rc(p)].mi);}
void build(int id,int l,int r)
{
	t[id]={l,r,0x3f3f3f3f};
	if(l==r){t[id].mi=a[l];return ;}
	int m=l+r>>1;
	build(lc(id),l,m);build(rc(id),m+1,r);
	pu(id);
}
int query(int p,int l,int r)
{
	if(r<t[p].l||t[p].r<l)return 0x3f3f3f3f;
	if(l<=t[p].l&&t[p].r<=r)return t[p].mi;
	return min(query(lc(p),l,r),query(rc(p), l,r));
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	build(1,1,n);
	while(q--)
	{
		int l,r;scanf("%d%d",&l,&r);l++;
		printf("%d\n",query(1,l,r));
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
const int N=5e5+10,inf=1e9;
struct node{int l,r,s;}tr[N<<2];int a[N];
void pushup(int p){tr[p].s=min(tr[lc(p)].s,tr[rc(p)].s);}
void bt(int p,int l,int r)
{
	tr[p]={l,r,inf};
	if(l==r){tr[p].s=a[l];return;}
	int mid=(l+r)>>1;
	bt(lc(p),l,mid),bt(rc(p),mid+1,r);
	pushup(p);
}
int query(int p,int l,int r)
{
	if(tr[p].r<l||tr[p].l>r)return inf;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].s;
	return min(query(lc(p),l,r),query(rc(p),l,r));
}
signed main()
{
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	bt(1,1,n);
	while(q--)
	{
		int x,y;cin>>x>>y;x++;
		cout<<query(1,x,y)<<'\n';
	} 
	return 0;
}

ST表

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int f[N][31];
int n,q;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    memset(f,0x7f,sizeof f);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
		int x;
		cin>>x;
    	f[i][0]=x;
		for(int j=1;(1<<j)<=i;j++){
	    	f[i][j]=min(f[i][j-1],f[i-(1<<(j-1))][j-1]);
		}
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		l++;
		int k=__lg(r-l+1);
        int ans=min(f[l+(1<<k)-1][k],f[r][k]);
        cout<<ans<<"\n";
	}
    return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int f[N][31];
int n,q;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    memset(f,0x7f,sizeof f);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        f[i][0]=x;
    }
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        l++;
        int k=__lg(r-l+1);
        int ans=min(f[l][k],f[r-(1<<k)+1][k]);
        cout<<ans<<"\n";
    }
    return 0;
}