RMQのST書き方と線分木書き方の2つのポーズ

RMQ問題は区間の最も値の問題を求めます
 
線分ツリーはO(logn)の時間的複雑さ内で問合せ操作を完了することができる.
しかしSTアルゴリズムは定数時間内に問合せ動作を完了することができる
 
STアルゴリズム:動的計画に基づいて区間最値を求めるアルゴリズム.
前処理とクエリーの2つの部分に分かれています
前処理:F[i][j]をiからi+2^j-1までの区間の最値として定義し、この2^jの区間は2つの部分の長さが2^(j-1)の同じ区間に分かれていると言える
区間1はi.....i+2^(j-1)-1区間2はi+2^(j-1).....i+2^j-1
F[i][j]=Max(F[i][j-1],F[i+2^(j-1)][j-1]が得る、境界条件はF[i][0]=A[i]である.
大きな区間は小さい区間で得るため、前処理時には区間長が増加する順にF[i][j]を繰り出す必要がある.
 
クエリー:区間[i,j]の最値を求めてd=(int)log 2(j-i+1)
i寄りの長さが2^d区間とj寄りの2^d区間の最大値をとり,両区間に共通部分が存在することができる
i,j max=Max(F[i][d],F[j-2^d+1,d])
 
問題:区間内の最大最小値の差を見出すこと.
2つの配列で区間の最大値と最小値をそれぞれ保存
詳細コードは次のとおりです.

#include<stdio.h>
#include<string.h>
#include<math.h>
#define lson l,m,p<<1
#define rson m+1,r,p<<1|1
#define Max(a,b) (a<b?b:a)
#define Min(a,b) (a<b?a:b)
#define INF 999999999

/*   
int N,M;
int MinP[50000*4+10],MaxP[50000*4+10];
int minT,maxT;

void Update(int val,int K,int l,int r,int p){
	int m=(l+r)>>1;
	if(l==r){
		MaxP[p]=MinP[p]=val;
		return;
	}
	if(K<=m)
		Update(val,K,lson);
	else
		Update(val,K,rson);
	MaxP[p]=Max(MaxP[p<<1],MaxP[p<<1|1]);
	MinP[p]=Min(MinP[p<<1],MinP[p<<1|1]);
}

void Query(int L,int R,int l,int r,int p){
	int m=(l+r)>>1;
	if(L<=l&&r<=R){
		minT=Min(minT,MinP[p]);
		maxT=Max(maxT,MaxP[p]);
		return;
	}
	if(L<=m)
		Query(L,R,lson);
	if(R>=m+1)
		Query(L,R,rson);
}

int main(){
	int i,val,a,b;
	scanf("%d %d",&N,&M);
	for(i=1;i<=N;i++){
		scanf("%d",&val);
		Update(val,i,1,N,1);
	}
	for(i=1;i<=M;i++){
		scanf("%d %d",&a,&b);
		minT=INF;
		maxT=0;
		Query(a,b,1,N,1);
		printf("%d
",maxT-minT);
	}
	return 0;
}


ST(    )*/
int N,M;
int A[50001];
int FMin[50001][20],FMax[50001][20];

void Init(){
	int i,j;
	for(i=1;i<=N;i++)
		FMin[i][0]=FMax[i][0]=A[i];
	for(i=1;(1<<i)<=N;i++){   //            
		for(j=1;j+(1<<i)-1<=N;j++){   //     
			FMin[j][i]=Min(FMin[j][i-1],FMin[j+(1<<(i-1))][i-1]);
			FMax[j][i]=Max(FMax[j][i-1],FMax[j+(1<<(i-1))][i-1]);
		}
	}	
}

int Query(int l,int r){
	int k=(int)(log(r-l+1)/log(2));
	return Max(FMax[l][k],FMax[r-(1<<k)+1][k])-Min(FMin[l][k],FMin[r-(1<<k)+1][k]);
}

int main(){
	int i,a,b;
	scanf("%d %d",&N,&M);
	for(i=1;i<=N;i++)
		scanf("%d",&A[i]);
	Init();
	for(i=1;i<=M;i++){
		scanf("%d %d",&a,&b);
		printf("%d
",Query(a,b));
	}
	return 0;
}

http://blog.csdn.net/zztant/article/details/8535764