借助倍增和動態規劃可以實現O（1）的時間復雜度的查詢

預處理：
①區間DP???轉移方程??f[i][j] = min(MAX同理)(f[i][j - 1],f[i + ][j - 1])??f[i][j]表示從i位置開始的后2^j個數中的最大值

用f[i][j]表示從j到j+2^i-1的最小值（長度顯然為2^i）。
任意一段的最小值顯然等于min（前半段最小值，后半段最小值）。
那么f[i][j]如何用其他狀態來繼承呢？
j到j+2^i-1的長度為2^i，那么一半的長度就等于2^(i-1)。
那么前半段的狀態表示為f[i-1][j]。
后半段的長度也為2^(i-1)，起始位置為j+2^(i-1)。
那么后半段的狀態表示為f[i-1][j+2^(i-1)]。

②不過區間在增加時，每次并不是增加一個長度，而是基于倍增思想，用二進制右移，每次增加2^i個長度?，最多增加logn次

這樣預處理了所有2的冪次的小區間的最值

?關于倍增法鏈接

查詢：
③對于每個區間，分成兩段長度為的區間，再取個最值（這里的兩個區間是可以有交集的，因為重復區間并不影響最值)

比如3,4,6,5,3一種分成3,4,6和6,5,3，另一種分成3,4,6和5,3，最大值都是6，沒影響。

首先明確 2^log(a)>a/2
這個很簡單，因為log(a)表示小于等于a的2的最大幾次方。比如說log(4)=2,log(5)=2,log(6)=2,log(7)=2,log(8)=3,log(9)=3…….
那么我們要查詢x到y的最小值。設len=y-x+1,t=log(len),根據上面的定理：2^t>len/2,從位置上來說，x+2^t越過了x到y的中間！
因為位置過了一半,所以x到y的最小值可以表示為min(從x往后2^t的最小值，從y往前2^t的最小值),前面的狀態表示為f[t][x]
設后面（從y往前2^t的最小值）的初始位置是k，那么k+2^t-1=y，所以k=y-2^t+1,所以后面的狀態表示為f[t][y-2^t+1]
所以x到y的最小值表示為f(f[t][x],f[t][y-2^t+1])，所以查詢時間復雜度是O（1）

④所以O(nlogn)預處理，O(1)查詢最值??但不支持修改
預處理時間復雜度O（nlogn），查詢時間O（1）。

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> using namespace std; int map[1000005][20]; int N,K; void work() {int i,j;for(j=1;1<<j<=N;j++)for(i=1;i+(1<<j)-1<=N;i++)//i+(1<<j)-1<=n是為了保證區間左端點不超出總數nmap[i][j]=min(map[i][j-1],map[i+(1<<j-1)][j-1]);//實質是動態規劃 } int question(int z,int y) {int x=int (log(y-z+1)/log(2));//注意y-z要加一才為區間長度return min(map[z][x],map[y-(1<<x)+1][x]);//分別以左右兩個端點為基礎，向區間內跳1<<x的最 //大值; } int main() {scanf("%d",&N);//輸入數據總數scanf("%d",&K);//輸入詢問次數kfor(int i=1;i<=N;i++)scanf("%d",&map[i][0]);//數據輸入加初始化，即從i開始向右走2的0次方的區間中的最大值，（注//意i到i的長度為一）。work();//預處理for(int i=1;i<=K;i++){int a,b;scanf("%d%d",&a,&b);printf("%d ",question(a,b));//輸出結果}return 0; }

?

?

總結

以上是生活随笔為你收集整理的疯子的算法总结14--ST算法（区间最值）的全部內容，希望文章能夠幫你解決所遇到的問題。

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