[洛谷P3865]【模板】ST表

复习板子. 远古代码概不负责.

ST表基于二进制划分思想, 用于求静态RMQ, $latex O(N\log N)$预处理, $latex O(1)$查询.

设$latex max[i][j]$表示区间$latex [i,i+2^j-1]$的最大值, 即从$latex i$开始长度为$latex 2^j$区间的最大值, 类似于树上倍增. 这个数组很容易预处理出来, 有DP方程$latex max[i][j]=max( max[i][j-1] , max[i+2^{j-1}][j-1] )$, 即左右两半合并.

求区间$latex [l,r]$的最大值时, 找出一个整数$latex t$使得 $latex 2^t <$ 区间长度 $latex <= 2^{t+1}$. 根据整数$latex t$的性质可知 : 以$latex l$开头的$latex 2^t$个数 和 以$latex r$结尾的$latex 2^t$个数 这两段一定覆盖了区间$latex [l,r]$, 取$latex max$即可.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址