ST 표

최근 며칠 동안 어떤 사내 가 33951 ℃ 에서 나 에 게 데이터 구 조 를 이야기 해 주 었 기 때문에 기 회 를 틈 타 블 로그 한 편 을 물 에 담 았 다.　　
원 리 를 알 게 되 었 습 니 다. 이 코드 를 보 는 것 은 정말 간단 합 니 다. 블 로 거들 도 주로 필 기 를 한 다음 에 원 리 를 알 지만 코드 능력 이 부족 하거나 알 수 없 는 WA 의 동료 들 에 게 이해 해 주 십시오.
ST 표 는 강력 한 정적 구간 의 가장 값 오프라인 조회 알고리즘 으로 데 이 터 를 처리 한 후에 조회 의 복잡 도 는 O (1) 에 불과 하고 얻 는 것 이 있 으 면 잃 는 것 이 있다. 소개 한 것 처럼 ST 표 는 오프라인 조회 만 지원 한다 (즉, 데이터 의 값 을 수정 할 수 없고 데 이 터 를 추가 / 삭제 할 수 없다). 원 리 는 매우 간단 하고 블 로 거들 도 그림 그리 기 가 귀 찮 으 며 인터넷 에서 도 비교적 좋 은 그림 을 가 진 상세 한 설명 을 찾 을 수 없다.(관심 있 는 동 료 는 ST 표 의 설명 을 직접 찾 아 볼 수 있 습 니 다) 그래서 과감하게 코드 를 말 합 니 다... (때 리 지 마 세 요) ST 표 템 플 릿 의 링크 를 제공 합 니 다. 로 곡 P3865 전송 문 은 먼저 2 의 n 제곱 을 미리 처리 하고 n 은 보통 20 보다 작 습 니 다.

pao[0]=1;
for(int i=1;i<=18;i++)
{
    pao[i]=pao[i-1]<<1;//   ，    2
}

한 배열 을 미리 처리 하면 lg [i] 는 i 보다 크 지 않 은 최대 2 의 멱 지 수 를 나타 낸다.

for(int i=2;i<=n;i++)
    {
        lg[i]=lg[i/2]+1;//          
    }

마지막 으로 DP 가 1 파 구간 의 최고 치 를 구 해 야 합 니 다.

int a=1,b=1;
    int hehe=lg[n];//             ，        
    for(int i=1;i<=hehe;i++)
    {
        a<<=1;
        for(int j=1;j<=n-a+1;j++)
        {//            ，               
        //              ，                
            st[j][i]=max(st[j][i-1],st[j+b][i-1]);
            //        ，          
        }
        b<<=1;
    }

사전 처리 가 끝 난 후 조회 작업 은 매우 간단 합 니 다. 조회 구간 에 포 함 된 두 개의 미리 처 리 된 구간 을 찾 아 비교 해서 최 치 를 구 하면 됩 니 다.

int find(int a,int b)
{
    int x=lg[b-a];
    int c=pao[x];//                   O(1)   
    int ans=max(st[a][x],st[b-c+1][x]);
    return ans;
}

이곳 을 볼 수 있 는 것 은 모두 진정한 사랑 입 니 다. 나리 들 께 감 사 드 립 니 다. 오 즈 에 게 무릎 을 꿇 었 습 니 다. 마지막 으로 복사 하기 편 한 코드 를 동봉 합 니 다.

#include
using namespace std;
int pao[20];
int lg[100005];
int st[200005][20];
int find(int a,int b)
{
    int x=lg[b-a];
    int c=pao[x];
    int ans=max(st[a][x],st[b-c+1][x]);
    return ans;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&st[i][0]);
    }
    pao[0]=1;
    for(int i=1;i<=18;i++)
    {
        pao[i]=pao[i-1]<<1;
    }
    for(int i=2;i<=n;i++)
    {
        lg[i]=lg[i/2]+1;
    }
    int a=1,b=1;
    int hehe=lg[n];
    for(int i=1;i<=hehe;i++)
    {
        a<<=1;
        for(int j=1;j<=n-a+1;j++)
        {
            st[j][i]=max(st[j][i-1],st[j+b][i-1]);
        }
        b<<=1;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        printf("%d
",find(a,b));
    }
    return 0;
}