ST算法：高效解决区间最值查询问题

ST算法是基于倍增原理的算法，广泛应用于解决静态空间的 区间最值查询问题（RMQ）。它通过预处理的方式，在**O(n log n)的时间复杂度内构建一个二维表，之后可以在O(1)**的时间复杂度内快速查询任意区间的最值。

什么是静态空间的`RMQ`问题？

给定一个长度为n的静态数列，进行m次查询，每次查询指定区间[L, R]（L, R ≤ n），要求返回该区间内的最值（最小值或最大值）。如果采用暴力搜索的方法，逐一比较区间内的每个数，单次查询的复杂度为O(n)，m次查询的总复杂度将达到O(mn)，效率非常低。

ST算法解决`RMQ`问题？

ST算法的原理如下：一个大区间若能被两个小区间覆盖，那么大区间的最值等于两个小区间的最值。如图所示，大区间{4,7,9,6,3,6,4,8,7,5}被两个小区间{4,7,9,6,3,6,4,8}和{4,8,7,5}覆盖，大区间的最小值为3，等于两个小区间的最小值min{3,4} = 3。

从以上原理，我们可以得到ST算法的基本思路，包括两个步骤：

（1）把整个数列分为很多个小区间，并提前计算出每个小区间的最值；

（2）对任意区间最值查询，找到覆盖它的两个小区间，由两个小区间的最值算出答案。

倍增法分块

把数列按倍增分为小区间

对数列的每个元素，把从它开始的数列分为长度为1,2,4,8… 的小区间。

图中给出了一个分区的例子，它按小区间的长度分成了很多组。

第一组是长度为1 的小区间，有n个小区间，每个小区间有1个元素.

第二组是长度为2的小区间，有n-1个小区间，每个小区间有2个元素。

第三组是长度为4的小区间，有n-3个小区间，每个小区间有4个元素。

依次类推一共有log2(n)组。

定义dp[s][k]表示左端点为s，长度为2^k的区间的最值。递推关系为

dp[s][k]=min{dp[s][k-1],dp[s+1>>(k-1)][k-1]}

我们不难看出，这是一个动态规划（DP）的过程。

2.查询任意区间的最值

（1）以任意元素为起点，有长度为1,2,4… 的小区间；以任意元素为终点，它前面也有长度为1,2,4，…的区间

（2）有以任意元素为起点的小区间，也有以任意元素为终点的小区间。

根据这个结论，可以把需要查询的区间[L,R]分为两个小区间，且这两个小区间属于同一组：以L为起点的小区间，以R为终点的小区间，让这两个小区间首尾相接覆盖[L,R]，区间最值由两个小区间的最值求得。一次查询的计算复杂度为O(1)

区间[L,R]的长度为len=R-L+1。两个小区间长度都为x，令x为比len小的2的最大倍数，有x <= len，且 2x >=len，这样保证能覆盖。另外，需要计算dp[][],根据dp[s][k]的定义，有2^k == x

1 2	int k = (int)log(double(R-L+1))/log(2.0) //int k = log2(L-r+1)

可以自己提前算出

1
2
3

LOG2[0] = -1;
for(int i = 1; i<= N; i++)
    LOG2[i] = LOG2[i >> 1] + 1;

最后可以给出区间[L,R]最小值的计算公式，等于覆盖它的两个小区间的最小值，即

min(dp[L][k], dp[R - (1 << k) + 1][k])

3.例题

问题描述：给定一个包含n个整数的数列和q个区间查询，查询区间内最大值和最小值的差

输入：第1行输入两个整数n和q；接下来n行中，每行输入一个整数hi，再后面q行中，每行输入两个整数a和b，表示一个区间查询

输出：对每个区间查询，返回区间内最大值和最小值的差

#include<bits/stdc++.h>
using namespace std;

const int N = 50005;
int n,m;
int a[N],dp_max[N][22],dp_min[N][22];
int LOG2[N];

void st_init(){
    //自己写的LOG2函数，向下取整
    LOG2[0] = -1;
    for(int i = 1; i <= N; i++) {
        LOG2[i] = LOG2[i>>1] + 1;
    }

    //初始化长度为1，即dp初始化
    for(int i = 1; i <= n; i++){
        dp_max[i][0] = a[i];
        dp_min[i][0] = a[i];
    }

    //dp过程
    for(int k = 1; k <= LOG2[n]; k++){
        for(int s = 1; s <= n - (1 << k)+1; k++){
            dp_max[s][k] = max(dp_max[s][k-1],dp_max[s+ 1<<(k-1)][k-1]);
            dp_min[s][k] = min(dp_min[s][k-1],dp_min[s+ 1<<(k-1)][k-1]);
        }
    }
}

//给定区间查询
int st_query(int L,int R){
    int k = LOG2(L-R+1);
    int x = max(dp_max[L][k], dp_max[R-(1<<k)+1][k]);
    int y = min(dp_min[L][k], dp_min[R-(1<<k)+1][k]);
    return x - y;
}

int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1; i<= n; i++){
        scanf("%d",&a[i]);
    }
    st_init();
    for(int i =1 ; i<=m ;i++){
        int L,R;
        scanf("%d %d",&L,&R);
        printf("%d\n",st_query(L,R));
    }
}

算法学习笔记-ST算法

ST算法：高效解决区间最值查询问题

什么是静态空间的RMQ问题？

ST算法解决RMQ问题？

倍增法分块

什么是静态空间的`RMQ`问题？

ST算法解决`RMQ`问题？