Posted on 2011-03-26 10:13
Mato_No1 閱讀(485)
評論(1) 編輯 收藏 引用 所屬分類:
經典問題的模型
今天終于搞懂了RMQ問題無比神犇的ST算法……
【離線RMQ問題】
題意：對于一個序列A[1..N]，共有M次提問，每次都是問A[l..r]（1<=l<=r<=N)中的最值，求出每次提問的答案。
（1）純暴力枚舉：O(NM)；
（2）樹狀數組：O(M(logN)^2)【見
樹狀數組解決離線RMQ問題】
（3）ST算法：O(MlogN)……
ST算法是基于分塊DP的。
設F[i][j]為A[i..(i+2^j-1)]（共2^j個元素）中的最值（前提是不能越界，即i+2^j-1 <= N），顯然F可以通過DP的方式得到：
F[i][j] = min||max{F[i][j-1], F[i+2^(j-1)][j-1]}
邊界：F[i][0]=A[i]。
DP求F的值的時間復雜度為O(NlogN)（一共只有NlogN個F值有意義）；
然后，對于求A[l..r]中的最值，只要將A[l..r]拆成若干連續的段，使得每段的長度都是2的整數次冪就行了，比如A[3..28]可以拆成A[3..18]、A[19..26]、A[27..28]三段，長度分別是16（2^4）、8（2^3）、2（2^1），所以min||max{A[3..28]} = min||max{F[3][4], F[19][3], F[27][1]}。
關鍵是怎么拆？方法：求出(r-l+1)（即A[l..r]的長度）的二進制形式，然后從高位到低位依次遍歷，如果找到1位就加上目前的位對應的冪，如(28-3+1)=(11010)2，所以依次找到F[3][4]、F[3+2^4][3]、F[3+2^4+2^3][1]。注意此時需要預先設一個數組B，B[2^i]=i，以方便找到某個取出的冪對應的指數。
顯然，最多只有logN段，所以一次提問的時間復雜度為O(logN)。
其實還有一種方法，就是先求出log(r-l+1)的值（下取整），設為x，然后F[l][x]和F[r-2^x+1][x]中的較大/較小值就是A[l..r]中的最值。這樣，一次提問的時間復雜度就降到了O(1)。問題是，系統log函數灰常慢，也許算一次log函數值的時間已經超過了logN，這樣顯然得不償失。所以仍然推薦上面的方法。
【核心代碼（以求最小值為例，最大值類似）】
分段法：
int MIN(int l0, int r0)
{
int min = INF, h = l0, d0, b0;
for (int d = r0 - l0 + 1; d; d -= d0) {
d0 = d & -d; b0 = B[d0];
if (F[h][b0] < min) min = F[h][b0];
h += d0;
}
return min;
}
求log值法：
int MIN(int l0, int r0)
{
int v = (int)floor(log2(r0 - l0 + 1.0)), s1 = F[l0][v], s2 = F[r0 - (1 << v) + 1][v];
return s1 <= s2 ? s1 : s2;
}
求F數組值的預處理代碼（注意，如果采用求log值的方法就不需要B數組了）：
void prepare()
{
re(i, n) F[i][0] = a[i];
int x;
re2(j, 1, MAXS) {
if ((1 << j) <= n) B[1 << j] = j;
x = n - (1 << j) + 1;
re(i, x) F[i][j] = min(F[i][j - 1], F[i + (1 << j - 1)][j - 1]);
}
}
【后經效率測試，發現當N=M=100000的隨機數據中，兩種方法都可以在0.4s以內得出正確結果，其中log值法比分段法略慢0.01s左右，相差不大，但考慮到“盡量少使用數學函數”的原則，仍推薦分段法】