ST算法

2022-03-06 算法

什么是ST？

这就是ST（大雾

ST的意思是“稀疏表（Sparse Table）”，是一种用来处理区间最值问题（Range Minimum Query，RMQ）的数据结构。假设一个数列一共有n个元素，在以 $O(nlogn)$ 的时间建立了一张稀疏表后，能以接近 $O(1)$ 的时间回答对于数列任意子区间最值的询问。

比如这道模板题。

这里询问的最值是子段的最大元素值，因此需要对子段的最大值先建一张ST表。用st[i][j]表示以i开头，长度为 $2^j$ 的子段的最大元素值。

稀疏表就“稀疏”在这个长度为 $2^j$ 。这样保证了可以在存储较少信息的情况下求取很大的区间最值，在j不超过35的情况下，就可以存储大小比整型范围还大的区间了。

这个稀疏表应该怎么求？以 $i$ 开头，长度为 $2^j$ 的子段可以分为以 $i$ 开头，长度为 $2^{j-1}$ 的子段，以及以 $i+2^{j-1}+1$ 开头，长度为 $2^{j-1}$ 的子段。以 $i$ 开头，长度为 $2^j$ 的子段的最大元素值就是这两个小子段的最大元素值中较大的那个。

用类似区间DP的方法，先求出每个长度较小的子段的最值，再通过这些最值来求长度较大子段的最值。

void ST_prework(int a[], int n, int st[][]) //a：数列。n：数列总的元素个数
{
    int i, j, t = log2(n); //数列总长度为n，j最大值就为t=log2(n)
    // 虽然t向下取整，但这点零头不影响后续求解。
    for (i = 1; i <= n; i++)
        st[i][0] = a[i];//以i为头元素，长度为1(2^0)的子段最大元素值就是头元素本身
    
    for (j = 1; j <= t; j++)//在外层枚举区间长度
    {
        for (i = 1; i <= n - (1 << j) + 1; i++)//待求区间的右端点不超过n
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
}

求出稀疏表后要如何快速得到区间最值？

对于下面这个数列

1	1 2 3 4 5 6

它的子段 $[1,4]$ 的最大元素值当然就是以1为头，长度为4的子段最大元素值，对应上面计算的st[1][2]。子段 $[1,5]$ 的最大元素值在上面没有对应的值，但它是以1为头，长度为4的子段最大元素值和以5为尾，长度为4的子段，即以2为头，长度为4的子段的最大元素值中较大的那个。

int ST_query(int l, int r, int st[][])
{
    int k = log2(r - l + 1);//以l为开头，长度为2的次方，且右端点不超过r的子段长度不超过2^k
    //k可以用倍增来求，用内置的log会更快
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

上面模板题的参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int st[100005][30], a[100005];
void ST_prework()
{
    int i, j, t = log2(n);
    for (i = 1; i <= n; i++)
        st[i][0] = a[i];
    for (j = 1; j <= t; j++)
    {
        for (i = 1; i <= n - (1 << j) + 1; i++)
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
}
int ST_query(int l, int r)
{
    int k = log2(r - l + 1);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main()
{
    int i, l, r, q;
    scanf("%d%d", &n, &q);
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    ST_prework();
    while (q--)
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", ST_query(l, r));
    }
    return 0;
}