• ST表(Sparse Table)是一種高效處理靜態數據區間查詢的數據結構，主要的作用是用于快速查詢區間的最值，區間GCD,區間按位與或

在這里以區間最大值為例子說明st表的模版

• 總體的思想就是定義dp[i][j]表示下標為i長度為2^j的區間的最大值，這個dp數組的定義的大小第一維度為原始的數組的長度(+1也可以)，第二個維度就是數組長度取log2然后+1，反正就是得取大點

初始化st表

def init_st(n)# 假設數組的下標從1開始for i in range(1,N):dp[i][0] = num[i]# 枚舉區間的長度,假設最大的長度不超過2^19for i in range(1,20):# 枚舉區間的開始的位置,原始的下標的范圍是 1到 n# 區間長度為2^i的時候，區間的最右邊的下標最大可以為n-(1<<i)+1for j in range(1,n-(1<<i)+2):# 分為兩部分，后面的那一半的開始位置是 j + 2^(i-1)dp[j][i] = max(dp[j][i-1],dp[j+(1<<(i-1))][i-1])

查詢操作

def query_st(l,r):k = int(math.log2(r-l+1))return max(dp[l][k],dp[r-(1<<k)+1][k])

區間最大值

區間最大值

• 直接套用模版

import math# 直接使用st表進行求解N,Q = map(int,input().split())a = [0] +  list(map(int,input().split()))dp = [[0]*(20) for _ in range(N+1) ]def init_stl():# 初始化st表# 定義dp[i][j]表示以i開始的，長度為2^j的區間的最大值for i in range(1,N+1):dp[i][0] = a[i]# 枚舉長度的冪次for i in range(1,20):# 枚舉開始的位置for j in range(1,N-(1<<i)+2):dp[j][i] = max(dp[j][i-1],dp[j+(1<<(i-1))][i-1])def query_stl(l,r):k = int(math.log2(r-l+1))ans = max(dp[l][k],dp[r-(1<<k)+1][k])return ansinit_stl()for _ in range(Q):l,r = map(int,input().split())print(query_stl(l,r))