ST表

st 表是解决 rmq 问题有力的工具
不支持在线修改，可以 \(O(1)\) 查询最值，\(O(nlogn)\) 预处理，只能处理静态区间最值。

st表用了倍增，动规的思想，以最大值为例。
\(st[i][j]\) 表示从 \(i\) 起，向后 \(2^j\) 个数中的最大值（包括 \(i\) 在内），也就是数组从下标 \(i\) 到下标 \(i + 2^j-1\) 中的最大值。

转移的时候，将当前区间拆成两半，分别取最值。
也就是区间 \([i, i + 2^{j-1}-1]\) 和 区间 \([i + 2^{j-1}, i + 2^j-1]\)，
\(st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1])\)

for(int i = 1; i <= n; i++)
    st[i][0] = a[i];
for(int j = 1; j <= 21; j++)
   for(int i = 1; i + (1 << j) - 1 <= n; i++)
       st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j -1]);

查询的时候，初始化中每一个状态的区间长度都是 \(2^j\),但是要查询的区间长度不一定是 \(2^j\)，
所以要引入一个定理：

\(2^{log(a)} > \frac a2\)

因为 \(log(a)\) 表示小于等于a的2的最大几次方。
比如说 \(log(4)=2, log(5)=2, log(6)=2, log(7)=2, log(8)=3, log(9)=3\)…….
那么我们要查询 l 到 r 的最大值。
设 \(len = r - l + 1,t=log(len)\)
根据上面的定理：\(2^t > len / 2\)
从位置上来说，\(l+2^t\) 越过了 x 到 y 的中间！
因为位置过了一半
所以l到r的最小值可以表示为 \(min(从l往后2^t的最小值， 从r往前2^t的最小值)\)
前面的状态表示为 \(st[l][t]\)
设后面（从 r 往前 2^t 的最小值）的初始位置是 k，
那么\(k+2^t-1=r\)，所以\(k=r-2^t+1\)
所以后面的状态表示为\(st[r-2^t+1][t]\)
所以x到y的最小值表示为 \(min(st[l][t],st[r-2^t+1][t]\))，所以查询时间复杂度是\(O（1）\)

洛谷P3865

#include <cstdio>
#include <iostream>
#include <cmath>
#define orz cout<<"AK IOI";

using namespace std;
const int maxn = 100010;
const int maxm = 2000010;

inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
	return x * f;
}
int n, m; 
int a[maxn], st[maxn][21];
int query(int l, int r)
{
	int k = log2(r - l + 1);
	return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main()
{
	n = read(); m = read();
	for(int i = 1; i <= n; i++)
	a[i] = read();
	for(int i = 1; i <= n; i++)
	st[i][0] = a[i];
	for(int j = 1; j <= 21; j++)
	   for(int i = 1; i + (1 << j) - 1 <= n; i++)
	   st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j -1]);
	for(int i = 1; i <= m; i++)
	{
	    int l, r;
	    l = read(); r = read();	
	    printf("%d\n",query(l, r));
	} 
	return 0;
}

第一个独立学会的知识点，祭！（虽然不难，而且很久之前老师讲过)
感谢 https://www.cnblogs.com/qq965921539/p/9608980.html
https://www.cnblogs.com/zwfymqz/p/8581995.html
https://blog.csdn.net/Hanks_o/article/details/77547380