ST表

ST表

ST表它是解决 RMQ 问题（区间最值问题）的一种强有力的工具。

时间复杂度为 $O(n \log n+Q)$。

实现过程

PS：以下讨论的是最大值，最小值同理。

建立一个 $dp$ 数组 $dp_{i,j}$ 表示从 $i$ 开始 $2^j$ 个数中的最大值。

边界为 $dp_{i,0}=a_i$，即从 $i$ 点开始 $2^0$ 个数中的最大值。

我们不难发现 $\max{\max{a_1 … a_{\frac{n}{2}}},\max{a_{\frac{n}{2}} … a_n}}}=\max{a_1…a_n}$。

那状态转移方程为：

$dp_{i,j}=\max{dp_{i,j-1},dp_{i+2^{j-1},j-1}}$。

其中 $dp_{i,j-1}$ 是前面一段，$dp_{i+2^{j-1},j-1}$ 是后面一段。

求最值

将该区间分成两个ST表，然后直接维护的小区间，然后二者求最值即可。

就是：$\max{f_{l,k},f[r−(2^k)+1][k]}$。