ST表

#include <iostream>
#include <algorithm>

using namespace std;

int a[1010];//原始输入数组
int st[1010][20];//st表

void init(int n)//初始化st表
{
    for (int i = 0; i < n; i++)
        st[i][0] = a[i];

    for (int j = 1; (1 << j) <= n; j++)//由前推后先枚举j
    {
        for (int i = 0; i + (1 << j) - 1 < n; i++)//i+(1<<j)-1为右边界
            st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);//前一半和后一半的最小值
    }
}

int search(int l, int r)
{
    int k = (int)log2(r - l + 1);
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}

int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        for (int i = 0; i < n; i++)
            cin >> a[i];

        init(n);

        while (m--)
        {
            int l, r;
            cin >> l >> r;
            cout << search(l, r) << endl;
        }
    }
    return 0;
}

2.

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>a(n);
vector<vector<int>>st;
int query(int l, int r) {
    int j = (int)log2(r - l + 1);
    return max(st[l][j], st[r - (1 << j) + 1][j]);
}
int main()
{
    cin >> n;
    a.resize(n);
    st.resize(n, vector<int>(log2(n) + 5));
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        st[i][0] = a[i];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
    int l, r;
    while (cin >> l >> r) {
        cout << query(l, r) << endl;
    }
}