poj 3264 Balanced Lineup(rmq vs 線段樹)

第一次做rmq問題，據說這道題是最簡單的rmq問題了。。。題意很簡單了，就是給一組資料，随即的求出某個區間内最大數和最小數之差。

查了許多資料，首先rmq原理：用A[1..N]表示一組數，F[I,J]表示從A[I]到A[I+2^J-1]這個範圍内的最大值，也就是以A[I]為起點連續2^J個數的最大值，由于元素個數為2^J個，是以從中間平均分成兩部分，每一部分的元素個數剛好為2^(J-1)個，整個區間的最大值一定是左右兩部分最大值的較大值，滿足動态規劃的最優原理狀态轉移方程：F[I,J]=max(F[I,J-1],F[I+2^(J-1),J-1])，邊界條件為F[I,0]=A[I]，僞代碼：

<a></a>

道理很簡單，╮(╯▽╰)╭。。。不知道我的代碼到底問題出哪裡了，第二組資料怎麼也過不去,，上網查了各路大神的代碼？？求指導，求排錯。。。。。下邊是我的有問題的代碼

View Code

rmq問題的标準解法是O(nlogn)的預處理, O(1)的查詢。不過線段樹可以實作O(nlogn)的預處理,O(logn)的查詢,速度也不錯。下邊是用線段樹寫的，效率沒有rmq快。