算法笔记--st表

概述：用倍增法求区间最值的离线算法，O(nlogn)预处理，O(1)访问。

预处理：

　　状态：st[i][j]：[i,i+2^j)之间的最值　　

　　状态转移：如果j等于0，st[i][j]=a[i]

　　　　　　　如果j大于0，st[i][j]=max(st[i][j-1],st[i+2^(j-1)][j-1])或st[i][j]=min(st[i][j-1],st[i+2^(j-1)][j-1])

访问：

　　求[l,r]区间里的最值

　　k=floor(log(r-l+1))

　　ans=max(st[l][k],st[r-2^k+1][k])或ans=min(st[l][k],st[r-2^k+1][k])

模板：

int st[N][],a[N];

void init_st(int n){

    for(int i=n;i>=;i--){

        st[i][]=a[i];

        for(int j=1;i+(<<j-)-<=n;j++){

            st[i][j]=min(st[i][j-],st[i+(<<j-)][j-]);

        }

    }

}

int query(int l,int r){

    int k=floor(log(r-l+)/log());

    return min(st[l][k],st[r-(<<k)+][k]);

}

例题：POJ - 3264

思路：求区间最值差

代码：

#include<iostream>

#include<cstdio>

#include<string>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=1e5+;

int ss[N][],st[N][],a[N];

void init_st(int n){

    for(int i=n;i>=;i--){

        st[i][]=a[i];

        ss[i][]=a[i];

        for(int j=;i+(<<j-)-<=n;j++){

            st[i][j]=min(st[i][j-],st[i+(<<j-)][j-]);

            ss[i][j]=max(ss[i][j-],ss[i+(<<j-)][j-]);

        }

    }

}

int query(int l,int r){

    int k=floor(log(r-l+)/log());

    return max(ss[l][k],ss[r-(<<k)+][k])-min(st[l][k],st[r-(<<k)+][k]);

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie();

    int n,q,l,r;

    cin>>n>>q;

    for(int i=;i<=n;i++)cin>>a[i];

    init_st(n);

    while(q--){

        cin>>l>>r;

        cout<<query(l,r)<<endl;

    }

    return ;

}

参考：https://www.cnblogs.com/AireenYe/p/6270518.html

巴特西

算法笔记--st表

最新文章

热门文章