ST表

休止 · 2018-10-23 21:54:10 · 个人记录

ST表用于静态查找，对于区间修改的操作无法支持

M[i][j]为从i位置起到2^j位置的区间中的最值，例如M[i][1]为i到i+1区间最值

#include<bits/stdc++.h>
#define ll long long
#define N 100010
using namespace std;
//ST表 -> 查询静态区间最值O（logn）预处理 O（1）查询 
inline int read()
{
    int x = 0,f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -f;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x*10 + ch-'0';
        ch = getchar();
    }
    return x*f;
}
int M[N][21];
int query(int li,int ri)
{
    int k = log2(ri-li+1);
    return max(M[li][k],M[ri-(1<<k)+1][k]);//查询左右区间最值 
    //li + (1<<k) - 1 = ri;
}
int main()
{
    int n,m;
    n = read(),m = read();
    for(int i = 1; i <= n; i++) M[i][0] = read();
    for(int j = 1; j <= 21; j++) //预处理
      for(int i = 1; i+(1<<j)-1 <= n; i++)
        M[i][j] = max(M[i][j-1],M[i+(1<<(j-1))][j-1]);//i到i+pow(2,j-1)-1 与 i+pow(2,j-1)到i+pow(2,j-1)-1
    for(int i = 1; i <= m; i++)
    {
        int l,r;
        l = read(), r = read();
        printf("%d\n",query(l,r));
    }
    return 0;
}