借助倍增和動態(tài)規(guī)劃可以實現(xiàn)O（1）的時間復(fù)雜度的查詢

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

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

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

這樣預(yù)處理了所有2的冪次的小區(qū)間的最值

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

比如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(tǒng)的最小值。設(shè)len=y-x+1,t=log(len),根據(jù)上面的定理：2^{t>len/2,從位置上來說，x+2}t越過了x到y(tǒng)的中間！
因為位置過了一半,所以x到y(tǒng)的最小值可以表示為min(從x往后2^{t的最小值，從y往前2}t的最小值),前面的狀態(tài)表示為f[t][x]
設(shè)后面（從y往前2^{t的最小值）的初始位置是k，那么k+2}t-1=y，所以k=y-2^{t+1,所以后面的狀態(tài)表示為f[t][y-2}t+1]
所以x到y(tǒng)的最小值表示為f(f[t][x],f[t][y-2^t+1])，所以查詢時間復(fù)雜度是O（1）

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

void ST_prework() {for (int i = 1; i <= n; i++) f[i][0] = a[i];int t = log(n) / log(2) + 1;for (int j = 1; j < t; j++)for (int i = 1; i <= n - (1<<j) + 1; i++)f[i][j] = max(f[i][j-1], f[i + (1<<(j-1))][j-1]); }int ST_query(int l, int r) {int k = log(r - l + 1) / log(2);return max(f[l][k], f[r - (1<<k) + 1][k]); }

總結(jié)

以上是生活随笔為你收集整理的『ACM-算法-ST算法』信息竞赛进阶指南--区间最值问题的ST算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。