ST表学习笔记

功能

ST表示用来求解给定区间RMQ的最值问题。

预处理复杂度:$O(nlongn)$，查询复杂度$O(1)$。

详解

原理

将原数组分成以2幂次的区间块，用$mn[i][j]$表示从$j$到$j-2^i-1$的最小值，最小值显然等于$$min(前半段最小值,后半段中最小值)$$从而得到递推式子

$$min[i][j]=min(mn[i-1][j],mn[i-1][j+2^{i-1}])$$

预处理代码

p[0] = 1;
rep(i,1,20) p[i] = 1<<i;
Log[0] = -1;
rep(i,1,200000) Log[i] = Log[i/2] + 1;
rep(i,1,n) mn[0][i] = a[i];
rep(i,1,n+1)
    rep(j,1,n+1)
    	if(j+p[i]-1 <= n)
            mn[i][j] = min(mn[i-1][j],mn[i-1][j+p[i-1]]);

查询

定理1:$$2^{log(a)}>a/2$$

查询$x$到$y$的最小值可以假设$len=y-x+1,t=log(len)$，根据定理1，$2^t>len/2$，那么位置过了一半之后最小值的可能就落在了$x$后面的$2^t$和$y$前面的$2^t$。式子为$$mmin = min(mn[t][x],mn[t][y-2^t+1])$$

实现

int t = Log[y-x+1];
int ans = min(mn[t][x],mn[t][y-p[t]+1]);

Reference:https://blog.csdn.net/hanks_o/article/details/77547380