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
关注
打赏