ST表

概念

$ST表是基于倍增思想，用于解决可重复贡献问题使用的一种数据结构$
$注意前提，必须离线，中途不可更改数据$
$最常见的就是解决区间最值RMQ问题以及区间gcd问题$

例题1、P3865 【模板】ST表

$这题主要掌握是牺牲空间去换不重复计算log2(n)的时间这个点$

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;

int st[N][21], Log2[N];

void pre() {
    Log2[1] = 0;
    Log2[2] = 1;
    for (int i = 3; i < N; ++i)    Log2[i] = Log2[i >> 1] + 1;
}

int main() {
    pre();
    int T = 1;
    //T = read();
    while (T--) {
        int n = read(), m = read();
        for (int i = 1; i <= n; ++i)    st[i][0] = read();
        int t = Log2[n]; //区间最长的2次方
        for (int j = 1; j <= t; ++j)
            for (int i = 1; i + (1 << j) - 1 <= n; ++i)
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        while (m--) {
            int l = read(), r = read();
            int s = Log2[r - l + 1];
            print(max(st[l][s], st[r - (1 << s) + 1][s]));
        }
    }
    return 0;
}

例题2、P1890 gcd区间

$st表处理区间GCD$

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 7;

int st[N][21], Log2[N];

void pre() {
    Log2[1] = 0;
    Log2[2] = 1;
    for (int i = 3; i < N; ++i)    Log2[i] = Log2[i >> 1] + 1;
}

int main() {
    pre();
    int T = 1;
    //T = read();
    while (T--) {
        int n = read(), m = read();
        for (int i = 1; i <= n; ++i)    st[i][0] = read();
        int t = Log2[n]; //区间最长的2次方
        for (int j = 1; j <= t; ++j)
            for (int i = 1; i + (1 << j) - 1 <= n; ++i)
                st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        while (m--) {
            int l = read(), r = read();
            int s = Log2[r - l + 1];
            print(gcd(st[l][s], st[r - (1 << s) + 1][s]));
        }
    }
    return 0;
}

例题3、P2880 [USACO07JAN]Balanced Lineup G

$给你n个数，m次查询，每次查询区间[l,r]中最大值于最小值的差$
$使用两个st表一个记录最大值一个记录最小值$

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 5e4 + 7;

int st1[N][21], st2[N][21], Log2[N];

void pre() {
    Log2[1] = 0;
    Log2[2] = 1;
    for (int i = 3; i < N; ++i)    Log2[i] = Log2[i >> 1] + 1;
}
int querymax(int l, int r) {
    int s = Log2[r - l + 1];
    return max(st1[l][s], st1[r - (1 << s) + 1][s]);
}
int querymin(int l, int r) {
    int s = Log2[r - l + 1];
    return min(st2[l][s], st2[r - (1 << s) + 1][s]);
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    pre();
    int T = 1;
    //T = read();
    while (T--) {
        int n = read(), m = read();
        for (int i = 1; i <= n; ++i)    st1[i][0] = st2[i][0] = read();
        int t = Log2[n]; //区间最长的2次方
        for (int j = 1; j <= t; ++j)
            for (int i = 1; i + (1 << j) - 1 <= n; ++i)
                st1[i][j] = max(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]),
                st2[i][j] = min(st2[i][j - 1], st2[i + (1 << (j - 1))][j - 1]);
        while (m--) {
            int l = read(), r = read();
            int ans = querymax(l, r) - querymin(l, r);
            print(ans);
        }
    }
    return 0;
}

$假设a[i]代表i年的降水量$
$注意分情况讨论，假设l为靠前的年份，r为靠后的年份$
$1、当l，r都不存在的时候直接输出maybe$
$2、当l存在，r不存在时，由题意可知r最大可以a[l],如果中间出现过不比a[l]小的降水量就是false，其余都是maybe$
$3、当l不存在，r存在时，只需要找中间是不是存在了不比a[r]小的降水量，如果存在就是false，不然就是maybe$
$4、当l，r都存在时，如果中间出现过的降水量都小于a[r]，并且中间不存在空格年份就是true，不然就是maybe$
$5、当l，r都存在时，如果中间出现过降水量大于等于a[r]，直接输出false$
$注意区间可能不存在，也就是l=r+1的时候，这个时候返回一个无穷小，别返回st[i][0]了$

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 5e4 + 7;

int year[N];
int st[N][21], Log2[N];

void pre() {
    Log2[1] = 0;
    Log2[2] = 1;
    for (int i = 3; i < N; ++i)    Log2[i] = Log2[i >> 1] + 1;
}
int query(int l, int r) {
    if (l > r)    return -INF;
    int s = Log2[r - l + 1];
    return max(st[l][s], st[r - (1 << s) + 1][s]);
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    pre();
    int T = 1;
    //T = read();
    while (T--) {
        int n = read();
        for (int i = 1; i <= n; ++i)    year[i] = read(), st[i][0] = read();
        int t = Log2[n]; //区间最长的2次方
        for (int j = 1; j <= t; ++j)
            for (int i = 1; i + (1 << j) - 1 <= n; ++i)
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        int m = read();
        while (m--) {
            int a = read(), b = read();
            int l = lower_bound(year + 1, year + 1 + n, a) - year;
            int r = lower_bound(year + 1, year + 1 + n, b) - year;
            if (year[l] != a and year[r] != b)    puts("maybe");
            else if (year[l] == a and year[r] != b) {
                if (query(l + 1, r - 1) >= st[l][0])    puts("false");
                else puts("maybe");
            }
            else if (year[l] != a and year[r] == b) {
                if (query(l, r - 1) >= st[r][0])    puts("false");
                else puts("maybe");
            }
            else if (st[l][0] >= st[r][0] and query(l + 1, r - 1) < st[r][0]) {
                if (r - l == b - a)    puts("true");
                else puts("maybe");
            }
            else puts("false");
        }
    }
    return 0;
}

力扣：找出最具竞争力的子序列

给你长度为 $n\leq1e5$ 的序列，你需要找到一个最小的长度为 $k$ 的子序列。
处理办法是 $ST$ 表预处理各个区间的最小值。
很显然，对于长度为 $n$ 的，我们要找到长度为 $k$ 的子序列，那么我们最低的要求就是在 $[1,n-k+1]$ 这个区间里面找到最小值，这样才有在最差的情况可以把后面全部的选上满足条件。并且满足了当前这个数是在这个区间中的最小数。每次都拿最小，我们就可以构成一个最小的子序列了。
注意枚举的起点和终点就可以了，查询区间最小值的过程使用 $ST$ 表处理。

const int N = 1e5+7;
int st[N][21], Log2[N];

void pre() {
    Log2[1] = 0;
    Log2[2] = 1;
    for (int i = 3; i < N; ++i)    Log2[i] = Log2[i >> 1] + 1;
}
int query(int l, int r) {
    int s = Log2[r - l + 1];
    return min(st[l][s], st[r - (1 << s) + 1][s]);
}
vector<int> ans;
int cnt[N];
class Solution {
public:
    int n;
    void dfs(vector<int>& nums, int start, int k) {
        if (k == 0)    return;
        int mini = query(start, n - k + 1);
        ans.push_back(mini);
        for (; nums[start - 1] != mini; ++start);
        dfs(nums, start + 1, k - 1);
    }
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        pre();
        memset(cnt, 0, sizeof cnt);
        n = nums.size();
        for (int i = 0; i < n; ++i)
            st[i + 1][0] = nums[i];
        int t = Log2[n];
        for (int j = 1; j <= t; ++j)
            for (int i = 1; i + (1 << j) - 1 <= n; ++i)
                st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        ans.clear();
        dfs(nums, 1, k);
        return ans;
    }
};

算法专项文章被收录于专栏

整合算法