• 原理
  可以用來(lái)求區(qū)間最值，類似線段樹(shù)，dp[ i ][ j ]的含義是從第i個(gè)數(shù)開(kāi)始的長(zhǎng)度為（1 << j）的區(qū)間的最值， 狀態(tài)轉(zhuǎn)移方程dp[ i ][ j ] = min(dp[ i ] [ j - 1 ] , dp[ i + (1 << ( j - 1) ) ][ j - 1]) 兩個(gè)循環(huán)預(yù)處理，在查詢某個(gè)區(qū)間時(shí)，因?yàn)樗樵兊膮^(qū)間的長(zhǎng)度不一定是2的次方，所以把區(qū)間分為兩個(gè)區(qū)間，保證能把原來(lái)的區(qū)間覆蓋

// 預(yù)處理 void ST(int n) {for (int i = 1; i <= n; ++i) {dp[i][0] = a[i];}for (int j = 1; j <= log2(n); ++j) {for (int i = 1; i + (1 << j) - 1 <= n; ++i) {dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);}} } // 查詢 int RMQ(int l, int r) {int len = r - l + 1;int x = log2(len);// 將查詢的區(qū)間分為兩個(gè)區(qū)間進(jìn)行查詢return min(dp[l][x], dp[r - (1 << x) + 1][x]); } 與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的RMQ-ST的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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