您当前的位置: 首页 > 

先求一个导

暂无认证

  • 1浏览

    0关注

    291博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

ST表模板

先求一个导 发布时间:2021-08-05 11:01:43 ,浏览量:1

ST表/RMQ:离线处理区间查询很好,但是没有线段树应用广,对于没有修改操作的题目可用。但是代码比较简单,比较适合我这种初学者。

核心: 对于具有结合律的可用,如最大值、最小值、gcd等。 f[i][j]数组,表示从i(下标)开始,区间长度为j的这一段的最大值(最小值). 第一维n,第二维logn,转移状态时间复杂度nlogn.

单次查询,O(1). 记得一定要预处理log!!!cmath库的log函数是logn级别的,被牛客某题卡了一下午QAQ,完全妹有想到是这个原因.

转移方程: f[i][j] = max(f[i][j-1],f[i+(1

关注
打赏
1662037414
查看更多评论
立即登录/注册

微信扫码登录

0.0387s