RMQ問題とSTアルゴリズム

RMQ(Range Minimm/Maximum Query)問題は区間の一番値を求める問題です.
長さnの配列Aに対しては、いくつかの照会が行われ、区間[L,R]に対しては、配列Aに下付き[L,R]の最小値が返される.
この問題は線分ツリーで解決できます.前処理の複雑さはO(nlogn)、クエリの複雑さはO(logn)です.
より良い解はSTアルゴリズムです.SparseTableアルゴリズム、すなわち、疎表アルゴリズムは、O(nlogn)の前処理後にO(1)の照会代に達することができる.
このアルゴリズムは非常に実現しやすい.
定義F[i,k]はiから始まり、長さは2^kです. の区間の要素の最小値を返します.
k=0の場合、F[i,0]の値は明らかにA[i]の値です.
k>0の場合、iからの長さが2^kの区間に対して、その最小値は明らかにiからの長さが2^(k-1)の区間の最小値とi+2^(k-1)からの長さが2^(k-1)の区間の最小値の中でより小さいものです.
すると、公式F[i,k]=min｛F[i,k-1],F[i+2^(k-1),k-1]が手渡されます.
2^k<=nのため、F配列の要素個数はnlognを超えないが、各要素はO(1)の時間内に計算できるので、合計時間はO(nlogn)である.

int F[maxn][20];
//   1   n
void RMQ_init(int A[],int n){
    for (int i=1;i<=n;i++) F[i][0]=A[i];
    for (int k=1;(1<<k)<=n;k++)
        for (int i=1;i+(1<<k)-1<=n;i++)
            F[i][k]=min(F[i][k-1],F[i+(1<<(k-1))][k-1]);
}

クエリー操作について ［L,R］は、kが2^k<=R-L＋1を満たす最大整数であると定義します.
Lで始まる長さが2^kの区間とRで終わる長さが2^kの区間で、完全なカバー区間[L,R]ができます.
したがって、この2つの区間の最小値のうち、より小さいのが、照会された区間［L,R］の最小値です.

int RMQ(int L,int R){
    int k=0;
    while ((1<<(k+1))<=R-L+1) k++;
    return min(d[L][k],d[R-(1<<k)+1][k]);
}

STアルゴリズムは、F配列に格納されている値を配列Aの下付きに変更すれば、最も値のある下付きスケーリングを求めることもできる.