RMQ-区間最値問題

区間最値クエリは,与えられた区間最値を求める問題である.総区間が[1,N]の場合、通常は複数回のクエリがあり、各クエリは異なる総区間のサブ区間である.
単純な方法は,各サブ領域間を遍歴して最値を見つけることであり,時間的複雑度はO(N)であるが,複数回のクエリがあると効率が低下する.この問題を解決する良いオンラインアルゴリズムはST(Sparse_Table)アルゴリズムである.
アルゴリズム思想
プリプロセッシング
STアルゴリズムはO(nlogn)の前処理後にO(1)のクエリ効率を実現できる.つまり,大量の区間の最値をあらかじめ求めておき,その後クエリ時に直接取得することができる.では、まず前処理がポイントです.
STアルゴリズムは動的計画の考え方を用いた:まずいくつかの区間の最小値を計算し、それから各問合せ区間をいくつかの最小値を計算した区間に分割し、これらの区間の最小値の最小値を統計し、それによって答えを得る.より効率的でより高速な前処理のために,各前処理の区間長を2の非負の整数次べき乗としたので,d[i][j]は区間[i,i+2^j−1]の最小値を表すように設定した(本稿では,いずれも最小値を求めると仮定する).ゲージ方程式を得ることができます

        d[i][j] = min(d[i][j-1],d[i+2^j][j-1])(j>=1)

d[i][j-1]はd[i][j]前半区間の最小値を表し、d[i+2^j][j-1]は後半区間の最小値を表す.例えば,要求区間[1,8]の最値は,[1,4]と[5,8]の最値を求め,[1,4]を[1,2],[3,4],[5,8]に分解して[5,6],[7,8]に分解することができる.ゲージに変換するプロセスは次のとおりです.

d[1,3]= min(d[1,2],d[5,2])

d[1,2] =min(d[1][1],d[3][1])

d[5,2] = min(d(5,1),d[7,1])

d[1][1] = min(d[1][0],d[2][0])

d[3][1] = min(d[3][0],d[4][0])

d[5][1] = min(d[5][0],d[6][0])

d[7][1] = min(d[7][0],d[8][0])

分解はこのように行われるが,前処理の計算過程は下から上へと実行される.
jの遍歴範囲は[1,log(N)],iの遍歴範囲[0,N+1−2^j]である.従って、得る前処理の時間的複雑度はO(nlgn)である.
区間の初期値(f[i][0]=i)は既知であり、全体のSTアルゴリズムの前処理ステップコードは以下の通りである.

for (int i = 0; i < N; ++i) {
        f[i][0] = a[i];
}

for (int j = 1; (1 << j) <= N; ++j) {
        for (int i = 0; i + (1 << j) - 1 < N; ++i) {
            f[i][j] = min(f[i][j-1], f[i+(1 << (j-1))][j-1]);
        }
}

区間の最値を求めます
前処理後、クエリのたびに答えがすばやく求められます.[a,b]間の最小値を問い合わせると、min(f[a,k],f[b-2^k+1,k])を求めることにより、Kが2^k<=b-a+1を満たす最大値であり、f[a,k]とf[b-2^k+1,k]に対応する区間が[a,b]全体を覆うことができる.したがってk=trunc(log_2(b-a+1)=trunc(ln(b-a+1)/ln(2))となる.評価コードは簡単ですが、ここでは貼りません.
まとめ
STはバイナリおよびダイナミックプランニング思想,区間最値の種々の特性を巧みに利用し,コード複雑度を低減し,その好適な応用例は2つのノードの最小共通親ノードを求めることである.