利用st表求最大最小值模板

ST表是一种用于快速查询区间最值的数据结构。它的核心思想是对区间进行预处理，将区间内的最值信息存储在一个二维数组中，然后利用这个数组进行查询。以下是一个求最大值的ST表模板代码：

const int MAXN = 100005;
const int MAXLOGN = 20;

int a[MAXN];
int st[MAXN][MAXLOGN];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        st[i][0] = a[i];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        }
    }
}

int query(int l, int r) {
    int k = log2(r-l+1); // k为最大的2的幂次方，使得2^k <= r-l+1
    return max(st[l][k], st[r-(1<<k)+1][k]);
}

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

这段代码中，init函数用于初始化ST表，query函数用于查询区间最大值。具体来说，init函数的实现如下：

1. 将a[i]的值存储到st[i][0]中，表示区间[i,i]的最大值为a[i]。

2. 对于每个j，计算区间[i,i+2^j-1]的最大值，存储在st[i][j]中。可以发现，区间[i,i+2^j-1]可以拆分为两个长度为2^(j-1)的子区间，即区间[i,i+2^(j-1)-1]和区间[i+2^(j-1),i+2^j-1]。因此，区间[i,i+2^j-1]的最大值等于区间[i,i+2^(j-1)-1]的最大值和区间[i+2^(j-1),i+2^j-1]的最大值中较大的一个。

query函数的实现也比较简单，首先计算k，然后查询区间[l,r]的最大值，等价于查询区间[l,l+2^k-1]的最大值和区间[r-2^k+1,r]的最大值中较大的一个。

求最小值的ST表模板代码与求最大值的类似，只需要将max改为min即可。