首页 > 其他 > 详细

浅见ST

时间:2019-08-26 07:11:08      阅读:76      评论:0      收藏:0      [点我收藏+]

ST算法流程

预处理

  ST算法其实是动态规划,我们用a数组来表示一组数字,设f[i][j]表示从a[i]开始到a[i + 2 ^ j - 1]这个范围内的最大值,即从i位置开始连续2 ^ j个数中最大的数字。由于元素个数为2^j个,所以我们可以把它分成2部分,每一部分的长度为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],这样我们就可以在时间复杂度为O(nlogn)内处理f数组

询问

  若我们需要查询区间[l, r]的最大值, 则需要求出最大的x满足2 ^ x <= r - l +1,那么,区间就会变成[l, l + 2 ^x - 1]和[l + 2 ^ x, r]两部分,如图所示:

技术分享图片

  两个区间的元素都为2 ^ x,所以区间[l, r]的最大值为max(f[l][x], f[r -  2 ^ x  + 1][x]),可以在O(1)内计算,所以ST是一种运行速度比线段树要更快的算法,但是ST不支持修改,这就是ST算法只适合用于求区间的值的原因

  求区间[x, y]最大值,表达式为:

  k = log2(y - x + 1)

  ans = max(f[x][k], f[y - 2 ^ k + 1][k])

模板

技术分享图片

 

浅见ST

原文:https://www.cnblogs.com/-sheldon/p/11409065.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!