RMQ(Range Minimum/Maximum Query)

ST表：
对于二元函数 $f(x, y)$ 来说，$x$ 表示第 $x$ 个数， $y$表示从$x$开始数后$2^y$个数（这也叫跳表的原因），获取这个区间的最值相当于获取这个区间的两半各部分的最值的最值，由此可以得到状态转移方程：

$$ f(x, y) = \max(f(x, y - 1), f(x + 2^{y - 1}, y - 1) $$

建ST表代码

void init(){
    for (int i = 0; i < M; i ++ )
        for (int j = 1; j + (1 << i) - 1 <= n; j ++ )
            if (!i) f[j][i] = a[j];
            else 
                f[j][i] = max(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
}

查询

如果要查询区间 $[l, r]$ 的最值，那么同样也是分开两部分查询：

$$ len = r - l + 1 $$

$$ k = log_{2}{len} $$

$$ query(l,r) = \max(f(l, k), f(r - 2^k + 1, k)) $$

查询代码

int query(int a, int b){
    int len = b - a + 1;
    int k = log(len) / log(2);

    return max(f[a][k], f[b - (1 << k) + 1][k]);
}

完整代码
时间复杂度：$O(N\log N)$

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, M = 18;

int a[N], f[N][M];
int n;

void init(){
    for (int i = 0; i < M; i ++ )
        for (int j = 1; j + (1 << i) - 1 <= n; j ++ )
            if (!i) f[j][i] = a[j];
            else 
                f[j][i] = max(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
}

int query(int a, int b){
    int len = b - a + 1;
    int k = log(len) / log(2);

    return max(f[a][k], f[b - (1 << k) + 1][k]);
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++ )  cin >> a[i];

    init();

    int q;
    cin >> q;
    while (q -- ){
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << endl;
    }

    return 0;
}

线段树做法(线段树模板题)

时间复杂度：$O(\log N)$

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, M = 4 * N;

int input[N];

struct node{
    int l, r, data;
}tree[M];

void build(int n, int l, int r){
    if (l >= r){
        tree[n].data = input[l];
        tree[n].l = tree[n].r = l;
        return ;
    }

    int lt = n << 1, rt = lt | 1;
    int mid = l + r >> 1;

    tree[n].l = l, tree[n].r = r;

    build(lt, l, mid), build(rt, mid + 1, r);

    tree[n].data = max(tree[lt].data, tree[rt].data);
}

int query(int n, int l, int r){
    if (tree[n].l >= l and tree[n].r <= r)
        return tree[n].data;

    int lt = n << 1, rt = lt | 1;
    int lData, rData;
    lData = rData = INT_MIN;
    if (tree[lt].r >= l)
        lData = query(lt, l, r);
    if (tree[rt].l <= r)
        rData = query(rt, l, r);

    return max(lData, rData);
}

int main(){
    int n, q;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> input[i];

    build(1, 1, n);

    cin >> q;
    while (q -- ){
        int a, b;
        cin >> a >> b;
        cout << query(1, a, b) << endl;
    }

    return 0;
}