Sparse Table
给一组数据，要求高效查询某区间内的最值，这种问题为RMQ（Range Maximum/Minimum Query）问题，ST表（Sparse Table）即为解决该问题的数据结构。
ST使用了动态规划与倍增的思想。假设数据大小为$n$，令动态规划矩阵$dp[idx][pow]$表示从第$idx$个数起之后$2^{pow}$个数之间的最值，即：
\[dp[idx][pow]=max([idx,idx+2^{pow}-1])\]易得当$pow=0$时，$dp[\cdot][0]$等于原数据；
当$pow=1$时，每个$dp[\cdot][1]$表示的是两个元素位置区间的最值，可得$dp[0][1]=max(dp[0][0],dp[1][0])$，$dp[1][1]=max(dp[1][0],dp[2][0])$，…，$dp[n-2][1]=max(dp[n-2][0],dp[n-1][0])$；
当$pow=2$时，每个$dp[\cdot][2]$表示的是四个元素位置区间的最值，由于$dp[\cdot][1]$已经计算好了每两个元素位置区间的最值，因此只需要两个低阶dp值即可更新高阶dp值。$dp[0][2]=max(dp[0][1],dp[2][1])$，…，$dp[n-4][2]=max(dp[n-4][1],dp[n-2][1])$；
由此可得dp递推式为：
\[dp[idx][pow]=max(dp[idx][pow-1],dp[idx+2^{pow-1}][pow-1])\]建好dp数组之后就是查询最值，给定查询区间$[l,r]$，至多只需要查询两个能够覆盖$[l,r]$区间的dp值即可。