RMQ問題のSparse_Tableアルゴリズム

RMQ問題,フルネーム(Range Minimum/Maximum Query)は,与えられた区間の中で最も値を求める問題である.
主な方法と複雑度は以下の通りである.
1、素朴(すなわち検索)、O(n)-O(qn)online.
2、線分樹、O(n)-O(qlogn)online.
3、Sparse_Table(実質的に動的計画),O(nlogn)−O(1)online.
4、RMQ標準アルゴリズム:まずLCA(Lowest Common Ancestor)、それから制約RMQ、O(n)-O(1)onlineとする.
昨日3つ目のSTアルゴリズムを習ったばかりです.
STアルゴリズムはO(nlogn)の前処理後にO(1)のクエリー効率を実現することができ,それによってクエリー回数が100万より多い(例えば100万より大きい)RMQ問題を解決する.
まず、前処理です.前処理はdpの考え方を採用し,区間[i,i+2^j−1]の最大値(すなわちiから長さ2^jの閉区間)をf[i][j]で表す.
開始時、f[i][0]はnum[i]に等しいに違いない.はい、初期値が見つかりました.次は状態遷移方程式です.
f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1]).すなわち[i,i+2^j-1]区間を2つの部分[i,i+2^(j-1)-1]と[i+2^(j-1),i+2^(j-1)+2^(j-1)-1]に分けて,ちょうど元の区間と一致する.
初期値と遷移方程式があれば,すべてのf[i][j]の値を底から上に渡すことができる.
境界については、もう少し注意しなければなりません.区間長は最大nであるため、2次元境界は最大log(n)/log(2.0)である.
1次元境界は,各開始点に対してnを見つける長さがあればよい,すなわちi+2^j−1<=nとすればよい.
そしてクエリーです.区間[a,b]の最大値をクエリすると仮定すると、区間の長さは2の整数べき乗ではない可能性が高いため、区間を長さ2の整数べき乗の2つの部分に分割し、この2つの区間の並列セットは[a,b]でなければならない.このスキームを実現するためには,2^k<=(b−a+1)に区間を2つの部分[a,a+2^k−1]と[b−2^k+1,b]に分割し,a,b区間の範囲を超えず,区間をすべてカバーできるようにする最大のkを求める必要がある.したがって,[a,b]区間の最大値は,上記2つの区間の最大値のうち最大値に等しい.(ちょっと回ります)
弱々しくコードを貼って,みんなに批判して指摘させる.

#include <math.h>
#include <stdio.h>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
const int N=100005;
int n,Q,c[N],a,b;
int dp_max[N][20];  //20       。    log(N)/log(2)
int dp_min[N][20];  
void Init()
{
    for(int i=1;i<=n;i++)
        dp_max[i][0] = dp_min[i][0] = c[i];
    double limit = log(n)/log(2.0);
    for(int j=1;j<=(int)limit;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            dp_max[i][j] = max(dp_max[i][j-1],dp_max[i+(1<<(j-1))][j-1]);
            dp_min[i][j] = min(dp_min[i][j-1],dp_min[i+(1<<(j-1))][j-1]);
        }
}
int Get_Max(int a,int b)
{
    int k = (int)(log(b-a+1)/log(2.0));
    return max(dp_max[a][k],dp_max[b-(1<<k)+1][k]);
}
int Get_Min(int a,int b)
{
    int k = (int)(log(b-a+1)/log(2.0));
    return min(dp_min[a][k],dp_min[b-(1<<k)+1][k]);
}
int main()
{
    scanf("%d%d",&n,&Q);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    Init();
    while(Q--)
    {
        scanf("%d%d",&a,&b);
        printf("%d
",Get_Max(a,b)-Get_Min(a,b));
    }
    return 0;
}