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快。