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
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?