ST算法用于区间最值问题,在O(N log N)的预处理后能以O(1)在线回答数列A中下标l~r之间的数的最大值
该算法利用了倍增的思想
初始化
设F[i,j]表示从i开始的2^j个数的最大值 即子区间[i,i+2^j-1]的最大值
递推边界 F[i,0]=A[i]
在递推时,我们把子区间成倍增长,有
F[i,j]=max(F[i,j-1],F[i+2^j,j-1])
即长度为2^j的子区间左右两端长度为2^(j-1)的子区间中值较大的那一个
询问
在询问任意区间[l,r]时,先计算一个k,满足2^k<r-l+1<=2^(k+1)
也就是使2的k次幂小于区间长度的前提下最大的k
那么从l开始的2^k个数 和 以r结尾的2^k个数这两段一定覆盖了整个区间[l,r]
这两段的最大值分别为F[l,k]和F[r-2^k+1,k]二者较大即所求
代码
1 | #include <cstdio> |