[Acwing] AcWing 1273. 天才的记忆 ST表

前言

传送门 :

介绍

S T ST ST表基于倍增的思想,可以做到 O n l o g n Onlogn Onlogn的预处理, O ( 1 ) O(1) O(1)的查询,不支持修改

思路

对于这种很常见的 R M Q RMQ RMQ问题,我们一般会如下操作 :

状态表示:

f [ i ] [ j ] f[i][j] f[i][j] 表从以 i i i为端点,向右跳 2 j − 1 2^j-1 2j−1的区间中的最大值

状态转移 : f [ i ] [ j ] = a [ i ] ( j = = 0 ) f[i][j]=a[i] (j==0) f[i][j]=a[i](j==0) f [ i ] [ j ] = m a x ( f [ i ] [ j − 1 ] , f [ i + ( 1 < < j − 1 ) ] [ j − 1 ] ) f[i][j]=max(f[i][j-1],f[i+(1