首页 > 其他 > 详细

【模板】st表

时间:2018-09-22 19:03:49      阅读:175      评论:0      收藏:0      [点我收藏+]

今天学习了一下st表  其实好几天就一直看


用禚神仙的话来说:

ST表是一种用于处理静态RMQ问题(无修改区间最值问题)的最快数据结构,书写方便使用简单效率便捷。
其中其预处理复杂度为O(nlogn),查询复杂度为O(1)。总时间复杂度为O(nlogn)。
常数远小于树状数组、线段树等毒瘤数据结构。

 

st表不支持在线修改 不支持!!!!!

 

一种利用dp求解区间最值的倍增算法。

 

定义:f[i][j]表示i到i+2^j-1这段区间的最大值。这里必须是i到i+2的j次方-1  别问为什么 规定!!!

 

预处理:f[i][0]=a[i]。即i到i区间的最大值就是a[i]。

 

状态转移:将f[i][j]平均分成两段,一段为f[i][j-1],另一段为f[i+2^(j-1)][j-1]。

 

两段的长度均为2^j-1。f[i][j]的最大值即这两段的最大值中的最大值。

 

得到f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])。

 

【模板】st表

原文:https://www.cnblogs.com/_Yrh/p/9690800.html

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