ST表「从入门到入门 · 浅显理解」

ST 表是个好东西，虽然前些天 ldq 学长已经讲完啦，但是那天他讲了那么多，让智商受限的我完全没有全部接受，选择性的扔掉了一部分（其实不舍的扔，记不住QAQ）。

ST 表最简单的应用就是查询区间最大值（或着最小值，这里以最大值为例），它（单纯 ST 表自己）需要你先修改之后（如果有修改要求），得到一个确切数组之后，经过 O ( nlogn ) 的预处理，然后就可以做到 O ( 1 ) 查询啦。

ST 表的预处理操作：

对于一个有 n 个数的 a [ n ] ，如果需要用一个二维数组 f [ n ] [ t ] ，其中 n 是指的用这 n 个数，t 是指的 n 最大是 2 的多少次幂，即 2 ^ t >= n 向上取整。

数组 f [ n ] [ t ] 是用来干什么的呢？f [ i ] [ j ] 是指以 a [ n ] 中第 i 个数开始，长度为 2 ^ j 的最大值，这样就清楚了数组 f [ n ] [ t ] 中 t 的来源啦吧。

所以我们要做的第一步预处理中：

f [ i ] [ 0 ] 就是存的 a [ i ] 值自己。

f [ i ] [ 1 ] 就是存的从 a [ i ] 开始往后一个，即 a [ i ] 和 a [ i + 1 ] 的最大值

……

以此类推，就可以得到我们想要的数组 f [ n ] [ t ] 啦。

那么我们怎么去实现这个东西呢？不能一个个的去枚举吧，那样的话，还不如用线段树（我是这么想得H_H），当然啦，这个问题在 ST 表被想出来的时候就解决啦，那就是递推得到，先看一下代码（不理解没关系，慢慢看）。

int f[maxn][20];

int a[maxn];

int n;

void st()

{

    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]);

        }

    }

}

第一个 for 循环应该没什么理解障碍，就是上面说的把自己存进去，因为是 2 ^ 0 。

第二个是两个 for 循环，也就是递推的部分，我们这样子来实现：

f [ i ] [ j ] 代表以 a [ i ] 开始长度为 2 ^ j 的数里面的最大值，即 f [ i ] [ j ] = max ( a[ i ] , …… , a [ i + 2 ^ j ] )。

我们先看一个简单的例子：现在一个数列是 a [ ] = { 1 ，2，3，4，5} ，那么（下标）0 ～ 2的最大值 Max1 ，和 3 ～ 4 最大值 Max2，两个里面的最大值 Max 就是整个区间的最大值，这个很好理解吧！

那么我们回到求 f [ i ] [ j ] 上，这个问题就变的和这个一样子啦，不过就是需要改变一下长度，我们把这个长度 len = 2 ^ j 的区间分成长度分别为 len1 = 2 ^ ( j - 1 ) 和 len2 = 2 ^ ( j - 1 ) 的这两个区间，只要求出来这两个的最大值就可以像上面那样子得到最终结果啦。

所以我们就可以理解上面我说的意思啦：f [ i ] [ j - 1] 代表从 a [ i ] 开始前 2 ^ ( j - 1 ) 个元素的最值，f [ i + ( 1 << ( j - 1 ) )] [ j - 1 ] 就是后面这 2 ^ ( j - 1 ) 个元素里面的最值，这样子合并取个最大值，就是总的最大啦，也就是代码中的：f [ i ] [ j ] = max ( f [ i ] [ j - 1 ] , f [ i + ( 1 << ( j - 1 ) ) ] [ j - 1 ] ) 。

这里有几点需要注意的（自己xj说的，不对可以告诉我哈）：

第一点是大家都知道的，在预处理中控制第二维的循环，也就是 for ( int j = 1; j <= t; j ++) ，一般的话 t 取 20 左右就可以啦，你要是不放心就先计算一下再开数组一样的，这个一定要放在外面，因为我们要通过递推得到，如果放在里面的话，就得不到我们想要的结果啦（可以感觉一下子）。

第二点就是那个 f [ i ] [ j ] 这里可能有理解误区，就算是不够 2 的整数次幂也没有关系的，初始化或者边界处理一下就可以啦，最大值最小值对应上相应的初始化。

第三点是对于 1 << ( j - 1 ) 这个东西，这和求那个 t 的时候的意思一个样子啦，这样子写比较高大尚一些。

ST 表在预处理时采用倍增和DP思想。

ST 表查询操作：

关于查询操作，想一想怎么样子可以做到 O ( 1 ) 查询的呢。

先来看简单的栗子（简单的看懂啦，难得就可以啦）：

a [ ] = { 1，2，4，5，6，3，6，8，7，0 }，在这些数里面我们想知道 1 ～ 8（下标从 0 开始）的最大值。

如果我们已经用数组 f [ n ] [ t ] 存好啦，我们可以先计算一下长度可以是 2 的多少次幂，左端点是 x = 1，右端点是 y = 8，长度 m = log ( y - x + 1) / log ( 2 )，我们需要差的就是从 a [ x ] 开始 m 这么长的区间，由于 m 存在边界问题，所以我们还需要查的区间就变成 [ x ] [ m ] ，但是这样子查的话不免可能会漏掉东西而且预处理的结果我们也没有用到，所以我们把这个 m 的长的区间分成啦两个部分，也就可以利用预处理的结果啦。

所以区间就变成了 [ x ] [ x + 2 ^ m - 1 ] 和 [ y - 2 ^ m + 1] [ y ] ，这两个区间分别对应的数组 f [ n ] [ t ] 是 f [ x ] [ m ] 和 f [ y - ( 1 << m ) + 1 ] [ m ] （这个可能存在不是很好理解的问题，不过不要忘记啦 f [ i ] [ j ] 的意思，是指从 a [ i ] 开始的长度为 2 ^ j 的最值，这样就可以啦，实在不好理解，可以手动画一画）。

代码：

int query(int x, int y)

{

    int t = log(abs(y-x + 1))/ log(2);

    int a = f[x][t];

    int b = f[y - (1 << t) + 1][t];

    return max(a,b);

}

完整的代码（其实仅仅是一点点，可以戳我）：

const int maxn = 1000004;

int f[maxn][20];

int a[maxn];

int n;

void st()

{

    for(int i = 1; i <= n; i ++) f[i][0] = a[i];

    int t = log(n) / log(2) + 1;

    for(int j = 1; j < 20; 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]);

        }

    }

}

int query(int x, int y)

{

    int t = log(abs(y-x + 1))/ log(2);

    int a = f[x][t];

    int b = f[y - (1 << t) + 1][t];

    return max(a,b);

}

---------------------

作者：Mercury_Lc

就罗嗦这么多啦，还有好多作业QAQ（看在我这么惨的份上，要是转载，别忘记啦我的地址QWQ）

巴特西

ST表「从入门到入门 · 浅显理解」

最新文章

热门文章

巴特西

ST表 「 从入门到入门 · 浅显理解 」

最新文章

热门文章

ST表「从入门到入门 · 浅显理解」