P3865

[模板]ST表

題目大意：求[L,R]靜態區間最大值

做法：

1：定義：(f[i][j])表示([i,i+2^{j}?1])這段長度為(2^{j})的區間中的最大值。

2：(RMQ)問題：給定一個長度為(N)的區間，(M)個詢問，每次詢問([L_i,R_i])這段區間元素的最大值/最小值。(RMQ)的高級寫法一般有兩種，即為線段樹和(ST)表。本文主要講解一下(ST)表的寫法。(以區間最大值為例)ST表：一種利用(dp)思想求解區間最值的倍增算法。

3:預處理：(f[i][0] = a[i])。即([i,i])區間的最大值(a_i)

4:狀態轉移：將([i,j])分成兩段，設(k=log_2^{j-i+1})，一段為([i,i+2^{k}?1])，另一段為([j-2^k+1,j])。兩段的長度均為(2^{k})。([i,j])的最大值即這兩段的最大值中的最大值。

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+6;
int n,m,a[maxn],f[maxn][21];

void RMQ(int n)
{
    for(int j=1;j<=20;j++)
        for(int i=1;i<=n && i+(1<<j-1)<=n;i++)
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]); 
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[i][0] = a[i];
	}
    RMQ(n);
    for(int i=1;i<=m;i++)
	{
        int L,R;
        scanf("%d%d",&L,&R);
        int k = (int)(log((double)(R - L + 1)) / log(2.0));// 保證 可以覆蓋到i - j全部 數值 2^( 
		printf("%d
",max(f[L][k],f[R - (1 << k) + 1][k]));
	}
    return 0;
}

總結

以上是生活随笔為你收集整理的[ST表]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。