POJ 3264 Balanced Lineup ST表
題意：給一串數字，多次詢問，求區間最大值和區間最小值的差。
思路：RMQ問題，可以用O(N^2)的預處理，然後每次O(1)的查詢，可以用線段樹，O(N)的建樹，O(logN)的查詢，可以用ST表記錄，O(NlogN）的預處理，O(1)的查詢。
實際上ST表的預處理過程也是一個DP的過程dp[i][j]表示從第i位開始連續2^j位的區間最值。
預處理：dp[i][j]=min(dp[i][j],dp[i+2^j][j]），查詢：query(l,r)=min(dp[l][k],dp[r-2^k+1][k])，k保證2^k<=r-l+1且2^(k+1)>=r-l+1。
代碼：
#include
#include
#include
#define maxn 50010
using namespace std;
int stTable_min[maxn][32],stTable_max[maxn][32];
int preLog2[maxn],aa[maxn];
void st_prepare(int n,int *array)
{
preLog2[1]=0;
for(int i=2; i<=n; i++)
{
preLog2[i]=preLog2[i-1];
if((1<=0; i--)
{
stTable_min[i][0]=array[i];
stTable_max[i][0]=array[i];
for(int j=1; (i+(1<
