ST算法详解

在RMQ（区间最值问题）中，著名的ST算法可以很好的求得答案。但却不能维护最值，也就是说，过程中不能改变区间中的某个元素的值。对于需要大量询问的场景是非常适用的。接下来我们就来详细了解下 ST 算法的处理过程。

解析

假如给出下面长度为10的数组：
1 3 2 4 9 5 6 7 8 0
让我们求得 [3, 7] 之间的最大值，如果采取暴力的查找方式，复杂度为$ O(n) $，尽管看起来还可以，但当要求连续查询区间最大值时，时间就有点吃不消了。而ST算法的每次查询只需要$ O(1) $的复杂度。因为他预处理了一个DP数组，复杂度为 $ O(n\log n) $。

我们用 dp[i][j] 表示从 i 开始的 $2^j$ 个数的最值，表示 dp[i][j] “管辖” index = i 开始的 $2^j$ 个数字，那么很显然，任何一段区间都能被两个 dp 元素管辖到。比如上面说的 [3, 7]，就能被dp[3][2] (3 4 5 6) 和 dp[4][2] (4 5 6 7)管辖到，而 max(dp[3][2], dp[4][2])也就是[3, 7] 的最值了。

这样我们只需预处理一个 dp 数组就可以了，而这个预处理是一个动态规划的过程，转移方程为：
dp[i][j] = max(dp[i][j - 1], dp[ i + (1<<(j-1)) ][j - 1]);

下面给出ST算法的预处理代码：

void ST_prework() {
    for (int i = 1' i <= n; i++)
        f[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    for (int j = 1; j < t; j++)
        for (int i = 1; i <= n - (1<<j) + 1; i++)
            f[i][j] = max(f[i][j-1], f[i + (1<<(j-1))][j-1]);
}

而 dp 数组的预处理和 RMQ 的求解过程正好是个逆过程。当讯问任意区间 [l, r] 的最值时，我们先计算出一个 k，满足 $ 2^k < r - l + 1 \leq 2^{k+1} $，也就是使2的 k 次幂小于区间长度的前提下最大的 k。那么从“ l 开始的 $2^k$ 个数”和以“ r 结尾的 $ 2^k $ 个数” 这两段一定覆盖了整个区间[l, r]，我们可以用f[l][k]和f[r - (1<<k) + 1][k]表示，两者中较大的那个就是整个区间 [l, r] 的最大值。
查询代码如下：

int ST_query(int l, int r) {
    int k = log(r - l + 1) / log(2);
    return max(f[l][k], f[r - (1<<k) + 1][k]);
}

实战

这里我们用 POJ 上的一道ST算法模板题Balanced Lineup来练习。

Balanced Lineup

Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 67305 Accepted: 31260
Case Time Limit: 2000MS

Description

For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

Output

Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

Sample Input

Sample Output

1
2
3

6
3
0

题意：

给你 n 个数字，p 次询问每次询问给出 l 和 r ，输出数字区间[l, r]中最大值与最小值的差。

思路：

模板题，需要注意的就是输入数据有很多需要使用 scanf，否则会TLE。还有就是使用log函数时需要传递参数类型为double，所以需要转换一下类型。

代码

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int N = 50005;
int f1[N][32], f2[N][32], a[N];
double n;
void st()
{
    for (int i = 1; i <= n; i++) {
        f1[i][0] = a[i];
        f2[i][0] = a[i];
    }
    int t = log(n) / log(2.0) + 1;
    for (int j = 1; j < t; j++) {
        for (int i = 1; i <= n - (1 << j) + 1; i++) {
            f1[i][j] = max(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]);
            f2[i][j] = min(f2[i][j - 1], f2[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int query1(int l, int r)
{
    int k = log(r - l + 1.0) / log(2.0);
    return max(f1[l][k], f1[r - (1 << k) + 1][k]);
}
int query2(int l, int r)
{
    int k = log(r - l + 1.0) / log(2.0);
    return min(f2[l][k], f2[r - (1 << k) + 1][k]);
}
int main()
{
    int q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    st();
    int l, r;
    for (int i = 0; i < q; i++) {
        scanf("%d%d", &l, &r);
        int ans1 = query1(l, r);
        int ans2 = query2(l, r);
        printf("%d\n", ans1 - ans2);
    }
    return 0;
}

解析

实战