ST算法学习笔记

· · 个人记录

ST算法的本质是动态规划。

预处理：

f[i][j] = \max(i,i+2^j-1)

把 f[i][j] 分成 f[i][j-1] 和 f[i+2^{j-1}][j-1]

f[i][j]=\max(f[i][j-1],f[i+2^{j-1}][j-1])

边界： f[i][0]=a[i]

查询：(\max(a[l],a[l+1],...,a[r]))

找出最大的x满足 2^x \leq r-l+1
所以ans=\max(f[l][x],f[r-2^x+1][x])

so: k=log2(r-l+1) ans=\max(f[l][k],f[r-2^k+1][k])

技巧：

预处理： 

lg[0]=-1;
for(int i=1;i<=maxn;i++)
{
    lg[i]=lg[i>>1]+1;
}