ST 算法是一种高效求解 >RMQ 问题< 的算法

其预处理时间复杂度为 O(nlogn) 查询时间复杂度为 O(1)

在进行大量数据的查询时,是一种非常好的算法

其思路是类似采用 二分 的思路对各个区间进行预处理
在查询时(查询 (a,d) )通过查询 [a,c) 和 [b,d) (a<=b<=c<=d) 来获取结果

预处理

用 dp[i][k] 表示区间 [i,i+2^k-1] (也即 [i,i+2^k] ) 范围内的最值
显然, dp[i][0] = num[i] ( [i,i) 的最值就是第 i 个数)
其他情况有 dp[i][k] = compare( dp[i][k-1] , dp[i+2^(k-1)][k-1] )
( [i,i+2^k-1) 的最值来自 [i,i+2(k-1)-1) 和 [i+2^(k-1),i+2^k-1) )

注意,要 先循环 k 再循环 i

for(int k = 0;(1 << k) <= n;k++) {
    for(int i = 1;i + (1 << k) - 1 <= n;i++) {
        //dp[i][k] 为 (i,j)区间的最值
        if(k == 0) {
            Max[i][k] = Min[i][k] = num[i];
        } else {
            Max[i][k] = max(Max[i][k - 1],Max[i + (1 << (k-1))][k - 1]);
            Min[i][k] = min(Min[i][k - 1],Min[i + (1 << (k-1))][k - 1]);
        }
    }
}

查询

查询时,由于不能确保一定能恰好使用 [i,i+2^k-1) 的形式表示
因此可以拆开成两个 有交集 的区间,比较求得最值
因此要找到数 c 和 d 使得 a<=b<=c<=d 并且可以表示成 i+2^k-1 的形式
可以找到数 k 有 [a,2^k-1) 和 [b-2^k+1,b) 可以表示成符合的形式
可推出 k=log2(a+b+1)
也即

int k = (int)(log(b - a + 1.0) / log(2.0));

查询时只需要比较 dp[a][k] 和 dp[b-2^k+1][k] 即可

int k = (int)(log(b - a + 1.0) / log(2.0));
cout << "Max: " << max(Max[a][k],Max[b - (2<<k) + 1][k]) << endl;
cout << "Min: " << min(Min[a][k],Min[b - (2<<k) + 1][k]) << endl;