ST表

引入

给定 $n$ 个数，有 $m$ 个询问，对于每个询问，求出 $[l,r]$ 中的最大值。

我们都会暴力，直接枚举取 $\max$，但是复杂度最坏是 $O(n^2)$ 的，我们需要更优的做法。

思想

ST 表基于倍增思想，可以做到 $O(n\log n)$ 的预处理，然后 $O(1)$ 查询，总复杂度为 $O(n\log n + m)$ 。

我们如果是和倍增一样，每次跳 $2^i$ 步的话，我们询问的复杂度是 $O(\log n)$ 的，并没有比线段树优，由于预处理复杂度还不如线段树。

我们设 $f_{i,j}$ 表示区间 $[i,i + 2^j - 1]$ 的最大值。

显然 $f_{i,j} = a_i$。

我们通过倍增的思路，写出下面的转移方程：

\[f_{i,j} = \max(f_{i,j - 1}, f_{i + 2^{j-1},j-1})
\]

然后就可以用 $O(n\log n)$ 的复杂度进行预处理了。

对于每一个查询操作，我们把 $[l,r]$ 拆成两个询问，$[l,l + 2^s -1]$ 和 $[r - s^2 + 1, r]$，其中 $s = \left \lfloor \log_{2}(r- l +1) \right \rfloor $。这两个部分的较大值就是答案。

【模板】ST 表 - 洛谷

code:

#include <bits/stdc++.h>

#define int long long
#define N 1000100
#define endl '\n'

using namespace std;

int n, m, a[N], f[N][21];

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;}

inline int ask(int l, int r)
{
    int k = log2(r - l + 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

signed main()
{
    n = read(), m = read();
    for(int i = 1; i <= n; i ++) f[i][0] = read();
    for(int j = 1; j <= 20; 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]);
    for(int i = 1; i <= m; i ++)
    {
        int l = read(), r = read();
        cout << ask(l, r) << endl;
    }
    return 0;
}