ST算法模板

本文主要是介绍ST算法模板，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N];
int f[N][20];
int mp[N];

void ST_prework() {
    for(int i = 1; i <= n; i++)
        f[i][0] = a[i];
    int t = log(n) / log(2);
    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]);
}

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

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 0; i <= n; i++)
        mp[i] = log(i) / log(2);
    ST_prework();
    for(int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d%d" ,&l, &r);
        printf("%d\n", ST_query(l, r));
    }
    return 0;
}

这篇关于ST算法模板的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！