[模板] ST表

~~学了这么久还不会 $S T$ 表，药丸~~

$S T$ 表是一种用来求解 $R M Q$ 问题的 $O (l o g n)$ 算法，相比于线段树求解 $R M Q$ 问题要更简洁，码量小，常数也更小，是一种基于倍增思想的算法。

我们定义数组 $f [i] [j]$ 表示第 $i$ 个元素到第 $i + 2^{j}$ 个元素区间范围内极值，那么可以根据倍增思想轻松写出转移方程。

$f [i] [j] = f [i] [j - 1] + f [i + (1 << (j - 1)) + 1] [j - 1]$

查询请求也非常简单，我们将区间 $[l, r]$ 拆为长度为 $l o g_{2} (r - l + 1)$ 的两部分，最后合并答案即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 100000 + 10;
const int MAXK = 17 + 10;

int f[MAXN][MAXK];
int data[MAXN];
int n;

inline void ST_init(){
    for(register int i=1; i<=n; i++)
        f[i][0] = data[i];

    int maxj = log(n) / log(2) + 1;

    for(register int j=1; j<maxj; j++){
        for(register int i=1; i<= n - (1 << j) + 1; i++)
            f[i][j] = max(f[i][j-1], f[i+ (1 << (j - 1))][j-1]);
    }
}

inline int query(int l, int r){
    int j = log(r-l+1) / log(2);    
    return max(f[l][j], f[r - (1 << j) + 1][j]);
}

BLOG