[模板] ST表

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

$ST$ 表是一种用来求解 $RMQ$ 问题的 $O(log \ n)$ 算法，相比于线段树求解 $RMQ$ 问题要更简洁，码量小，常数也更小，是一种基于倍增思想的算法。

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

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

查询请求也非常简单，我们将区间 $[l, r]$ 拆为长度为 $log_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