ST算法

没有修改的区间最值
\(O(nlogn)\)预处理
\(O(1)\) 查询
\(f[i][j]\) : 从 \(i\) 开始长度 \(2^j\) 的范围内的最大值
预处理是 前后两部分 合并结果
查询的时候从前往后长度 \(T\) 和 从后向前长度 \(T\) 的两段区间 并
\(T\) 是接近 \(r-l+1\) 最大的二进制数

void st_pre() {
	for (int i = 1; i <= n; i++) f[i][0] = a[i] ;
	int M = log(n) / log(2);
	for (int j = 1; j <= M; 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]) ;
} 

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