ST表

ST表可以在静态空间中 \(O(log)\) 查询最值，但需要 \(O(nlogn)\)初始化。

前缀和皆知尽人需要可逆性，\(+\) 的逆运算 为 \(-\)， $\times $ 的逆运算为 \({\div}\)（非0）， ^的逆运算为 ^本身， 但\(max\) \(min\)，不具有逆运算。

所以ST表粉墨登场（

SL表利用的是倍增思想。任何一个数均可以写成 \(a_1 \times 2^0 + a_2 \times 2^1 + \dots + a_k \times 2^{k - 1}\)，就可以把最值用其拼接。

求取答案的部分相对简单，分解后在求值。也有简单办法，因为最值重合不影响，即可使用 cmath 中的 \(log2(x)\) 找到 \(\le x\) 的最大2的幂。

现在问题来到如何预处理。定义 \(f_{ji}\)，表示跨度和起点，当然跨度是 \(2^j\)。每次转移就是之前两端拼起来$ f[j][i] = max(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);$

#include <cmath>
#include <iostream>

using namespace std;

const int kMaxN = 1e5 + 5;

int n, m, a[kMaxN], f[kMaxN][30];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    f[i][0] = a[i];
  }
  for (int i = 1; (1 << i) <= n; i++) {            // 跨度
    for (int j = 1; j + (1 << i) - 1 <= n; j++) {  // 起点
      f[j][i] = max(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
    }
  }
  for (int i = 1, l, r; i <= m; i++) {
    cin >> l >> r;
    int u = log2(r - l + 1);
    cout << max(f[l][u], f[r - (1 << u) + 1][u]) << '\n';;
  }
  return 0;
}