ST表

1. $O(logn * n)$ 预处理 $2*10^6 \approx 2^{21}$ $log2^{21} = 21$
2. $O(1)$查询,不支持修改操作
3. 例如用于静态区间最大最小值查询

---

预处理

• 询问区间$[L,R]$,最多使用2个预处理过的区间的并就能覆盖询问区间

  $f(i,j)$表示区间$[i,i+2^j-1]$的最大值 ,,,, $2^j-1$即倍增的长度 ,,, $f(i,j) = max[i,i+2^j-1]$

  ---

  $f(i,0) = a_i$

  ---

  $f(i,j) = [i,i+2^j-1]$

  ​ $= [i,i+2^{j-1}-1] \cup [i+2^{j-1},i+2^j-1]$

  ​ $= [i,i+2^{j-1}-1] \cup [i+2^{j-1},i+2^{j-1}+2^{j-1}-1]$

  注意到：

  $[i+2^{j-1},i+2^{j-1}+2^{j-1}-1] = f(i+2^{j-1},j-1)$

  $[i,i+2^{j-1}-1] = f(i,j-1)$

  所以

  $f(i,j) = max(f(i,j-1),f(i+2^{j-1},j-1))$

询问

• 询问区间$[l,r]$,则区间长度$len = l-r + 1$,

  设$2^s = len = l-r+1$ -> $s = log(l-r+1)$

  分成2部分

  $[l,l+2^s-1] \cup [r-2^s+1,r] = [l,l+2^s-1] \cup [r-2^s+1,r-2^s+1 + 2^s-1]$

  $= max(f(l,s),f(r-2^s+1,s))$

---

• $s=log(l-r)$,应该是恰好平分了查询区间 (

Luogu st表

#include <bits/stdc++.h>
using namespace std;
const int LogN = 21;
const int maxn = 2e6+10;

int f[maxn][LogN],log_2[maxn];

void init() { // 预处理log2
    log_2[1] = 0;
    log_2[2] = 1;
    for (int i=3; i<maxn; ++i)
        log_2[i] = log_2[i/2] + 1;
}

int n,m;

int main() {
    init();
    scanf("%d%d",&n,&m);
    // 读入数列,静态区间
    for (int i=1; i<=n; ++i) scanf("%d",&f[i][0]);
    for (int j=1; j<=LogN; ++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]);
            //f[i][j] = max(f[i][j-1],f[i + 1<<(j-1)][j-1]);
    int x,y;
    while (m--) {
        scanf("%d%d",&x,&y);
        //int s = log_2[y-x+1];
        int s = log_2[y-x];
        printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s]));
    }
    return 0;
}