倍增 ST表

作者: Void_Caller | 来源:发表于2020-07-17 13:09 被阅读0次

引入

直接通过一道经典的例题来引入st表以及倍增的概念。

落谷P3865 ST表

描述

给定一个长度为 $N$ 的数列，和 $M$ 次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数 $N,M(1 \leq N \leq 10^5,1 \leq M \leq 2 \times 10^6)$ ，分别表示数列的长度和询问的个数。

第二行包含 $N$ 个整数（记为 $a_i(0 \leq a_i \leq 10^9)$ ），依次表示数列的第 $i$ 项。

接下来 $M$ 行，每行包含两个整数 $l_i, r_i$ ，表示查询的区间为 $[l_i, r_i]$

输出格式

输出包含 $M$ 行，每行一个整数，依次表示每一次询问的结果。

输入样例

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出样例

9
9
7
7
9
8
7
9

思路

如果用传统的思路去写这道题，那么无非就是每次都对区间进行一次遍历，那么复杂度将高达 $N\times M$ ，那一定会T掉，所以我们期望是先进行一遍预处理，然后每次通过 $O(logn)$ 或者是 $O(1)$ 的复杂度进行查询，从而挤进去。

倍增

这边，则需要引入一个倍增的思想，利用倍增进行预处理，则可大大节省查询所需的时间，也就是查询可以达到 $O(1)$ 的复杂度。

为了达到 $O(1)$ 的查询时间复杂度，那么我们就需要预处理一个表，蕴含所有区间的结果。

而倍增的独特之处在于，他在 $预处理$ 的时候时间复杂度仅仅只需要 $O(nlogn)$ ，而查询也只需要 $O(1)$ 。

定义

为了预处理出来一个表，那么我们先定义一下这个表的含义。

我们定义一个二维数组： $st[i][j]$ 是从 $i$ 开始，一直到 $i+2^j$ 这个区间的最大(小)值，也就是 $st[i][j]=max \{ [i,i+2^j) \}$

那么这个有什么用呢，先不着急，我们先想办法预处理出来这个表。

预处理

设我们的原数组是a[]，那么首先很显然的是 $st[i][0] = a[i];$

之后我们在进行递推，这边有一个公式 $st[i][j] = max\{st[i][j - 1],st[i + 2^{j-1}][j - 1]\}$

乍一看可能不是那么好理解，其实根据定义再结合一下几个直观的数字便可很容易明白他在做什么。

我们首先需要明白的是，一个区间内，不管是最小值还是最大值，该区间的最大(小)值都等于其所有子区间的最大(小)值的最大(小)值，即满足 $max\{range\}=max\{max\{subrange_1\},max\{subrange_2\},...,max\{subrange_n\}\}$

那么上述公式也很好理解了，根据定义st[i][j]是从 $i$ 开始到 $i+2^j$ 这个区间内的最大(小)值，所以他可以裂开成两个子区间，为了能够递推，所以我们裂开平分出两个长度为 $2^{j-1}$ 的子区间，很显然，这两个区间分别为 $[i,i+2^{j-1})$ 和 $[i+2^{j-1},i + 2^{j-1} + 2^{j-1})$ ，也即 $[i+2^{j-1},i+2^j)$ ，因此这两个区间恰好把原区间 $[i,i + 2^j)$ 给分开了。

图示

剩下的便是在代码上的处理了，代码不难理解，直接上吧。

#define rep(i,a,b) for (int i = a;i <= b;i ++)

const int MAXN = 100010;

int st[MAXN][20];
int a[MAXN];

void init() {
    // 定义 st[i][j] 是从i开始，到i + 2^j这一段，即[i,i + 2^j]这一段中的最大/小值
    rep(i,1,n) st[i][0] = a[i];

    for (int j = 1;(1 << j) <= n;j ++) { // 遍历所有的j，j是一个很小的数字，最大值=log2(n)
        rep(i,1,n - (1 << j) + 1) { // 在[1,n]区间范围内，确定j的情况下，把所有的i都遍历求值一遍
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); // 套公式
        }
    }
}

查询

查询这边也相应着有一个公式，若需要查询的区间左端下标是 $l$ ，右端是 $r$ ，则有 $x=\lfloor log_2(r-l+1)\rfloor$ $ans=max\{st[l][x],st[r - 2^x + 1][x]\}$

解释

我们想查询的区间是 $[l,r]$ ，也就是 $[l,r+1)$ ，st表的定义是 $st[i][j]=max\{[i,i + 2^j)\}$

那么上述公式中 $st[l][x] = max\{[l,l + 2^x)\}$ $st[r - 2^x + 1][x]=max\{[r - 2^x + 1,r+1)\}$

若 $x=log_2(r-l+1)$ ，那么上述公式描述的均是 $max\{[l,r+1)\}$ 。

而实际上 $x=\lfloor log_2(r-l+1)\rfloor$ ，而 $2^{\lfloor log_2a\rfloor}>\frac a2$ ，
所以答案 $ans$ 只需要求 $[l,l+2^x)$ 和 $[r - 2^x + 1,r+1)$ 这两段的区间最大值即可。

查询代码

int query(int l, int r)
{
    int x = log2(r - l + 1);
    return max(st[l][x],st[r - (1 << x) + 1][x]);
}

st模版

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <bitset>

using namespace std;

#define ll long long
#define lll __int128
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define INT_INF 0x7fffffff

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)

#define cio ios::sync_with_stdio(false); // Do not use it with "scanf" and other c input!
#define pb push_back
#define rep(i,a,b) for (int i = a;i <= b;i ++)
#define pre(i,a,b) for (int i = a;i >= b;i --)
#define REP(i,a,b) for (int i = a;i < b;i ++)

#define read(a,s,n) rep(i,s,n) scanf("%d",a + i);
#define READ(a,s,n) REP(i,s,n) scanf("%d",a + i);

#define read_ll(a,s,n) rep(i,s,n) scanf("%lld",a + i);
#define READ_ll(a,s,n) REP(i,s,n) scanf("%lld",a + i);

#define _T_(T) int T;scanf("%d",&T);while (T --)
#define _E_(T) while (~T)

#define Tprint(a,s,e) {int f=1;REP(i,s,e){if(f)f=0;else printf(" ");printf("%d",a[i]);}}


#define endl '\n'

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return
#define reutnr return


/* header_useful_h */

inline int read_int()
{
    int x = 0,f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

const int MAXN = 100010;

int st[MAXN][20];
int a[MAXN];

int n,m;

void init() {
    // 定义 st[i][j] 是从i开始，到i + 2^j这一段，即[i,i + 2^j]这一段中的最大/小值
    rep(i,1,n) st[i][0] = a[i];

    for (int j = 1;(1 << j) <= n;j ++) { // 遍历所有的j，j是一个很小的数字，最大值=log2(n)
        rep(i,1,n - (1 << j) + 1) { // 在[1,n]区间范围内，确定j的情况下，把所有的i都遍历求值一遍
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); // 套公式
        }
    }
}

int query(int l, int r)
{
    int x = log2(r - l + 1);
    return max(st[l][x],st[r - (1 << x) + 1][x]);
}

int main()
{
    scanf("%d%d",&n,&m);
    rep(i,1,n) {
        a[i] = read_int();
    }
    init();
    int l,r;
    while (m --) {
        scanf("%d%d",&l,&r);
        printf("%d\n",query(l, r));
    }
    return 0;
}

倍增 ST表

引入

描述

输入格式

输出格式

输入样例

输出样例

思路

倍增

定义

预处理

查询

解释

查询代码

st模版

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法