引入

给定你一个长度为n的数组a，再给你q次询问，每次询问给定你一个区间[L,R]，让你求a数组中L~R中的最大值/最小值

我们利用常规算法求时很显然会超时，以此我们需要一个数据结构——ST表来解决

ST表

ST表是一个类似于线段树的东西，但是它不支持动态更新，不过在面对静态时是一个很不错的选择，其代码量远小于线段树

ST表采用了倍增+dp的思想，利用倍增我们可以将时间复杂度从暴力的优化到

那么如何实现呢？（下面以最大值举例）

初始化

我们定义一个数组f[i][j]，其代表的是从 i 开始  长度区间内的最大值，即

根据倍增，我们可以知道每一次的步骤类似下图所示

 

 比如我们要求f[i][j]，我们可以求max(f[i][j-1],f[i+(1<<j)][j-1])

因为，所以显然我们可以这样将一个区间分为两个区间，以此类推

最后我们便可以求出所有f[i][j]了

查询

假如我们要查询L~R区间的最大值，大多数情况下R-L不一定是2的整数幂，那我们该如何解决呢？

我们可以考虑拼接思想，假如R-L的值为m，那么我们可以定义一个k，有 k = [log2(m)]

那么显然我们可以将 max(f[l][k],f[r-(1<< k)][k])做为答案，为什么呢？

我们可以画出以下图

 可以看出就算最大的时候也是两区间重合，最小的情况是刚好对半分，不过一般来说都有一部分交集，但是这部分交集显然对答案没影响，所以上述式子是可行的

于是我们便可以写出代码

代码

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

int n, m;
const int maxLog = 20;
const int MAXN = 100005;
int f[MAXN][maxLog];
int logN[MAXN];

void preLog()
{
    logN[1] = 0, logN[2] = 1;
    for (int i = 3; i < MAXN; i++)
    {
        logN[i] = logN[i / 2] + 1;
    }
}

void preF()
{
    for (int j = 1; j <= maxLog; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            f[i][j] = max(f[i][j-1],f[i + (1 << (j - 1))][j - 1]);
        }
    }
}
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}
void solve()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = read();
    }
    preLog();
    preF();
    for (int i = 0; i < m; i++)
    {
        int l = read(), r = read();
        int s = logN[r - l + 1];
        printf("%d\n", max(f[l][s], f[r - (1 << s) + 1][s]));
    }
}
int main()
{
    cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}