用线段树算区间最值代码

以下是一个用线段树算区间最值的示例代码，以查询区间最小值为例：

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100005;

int n, m;
int a[MAXN];
struct Node {
    int l, r, minn;
} tr[MAXN*4];

// 建立线段树
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) { // 叶子节点
        tr[u].minn = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u<<1, l, mid);
    build(u<<1|1, mid+1, r);
    tr[u].minn = min(tr[u<<1].minn, tr[u<<1|1].minn);
}

// 查询区间最小值
int query(int u, int ql, int qr) {
    if (ql <= tr[u].l && tr[u].r <= qr) { // 完全包含
        return tr[u].minn;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    int res = 0x3f3f3f3f; // 初始化为一个极大值
    if (ql <= mid) res = min(res, query(u<<1, ql, qr)); // 左子区间有交集
    if (qr > mid) res = min(res, query(u<<1|1, ql, qr)); // 右子区间有交集
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build(1, 1, n); // 建立线段树
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(1, l, r));
    }
    return 0;
}

这段代码中，建立线段树的过程采用递归方式实现，查询区间最小值的过程也采用递归方式实现。对于每个节点，维护该节点对应区间的最小值。查询区间最小值的过程，采用线段树的递归查询方式，将查询区间划分成若干个离散的单元，并依次查询每个单元，最终得到查询区间的最小值。