線形構造——ST表とRMQ

【概要】
RMQ(Range Minimum/Maximum Query)は、長さnの数列Aについて、何度かRMQ(i,j)への問い合わせに回答し、数列Aの中で区間[i,j]に下付きの最も値、すなわち、区間の最も値の問い合わせ問題を返す
現在RMQ問題を解決するためによく用いられている方法はSTアルゴリズム(Sparse Table)であり,STアルゴリズムを用いて打ち出されたテーブルを前処理してSTテーブルと呼ぶ.
【STアルゴリズム】
RMQ問題については,n個数m回の質問を与え,毎回質問区間が最も値が高く,mが小さい場合は暴力を用いて解決できるが,mが大きくなるにつれてO(logn)の質問処理が不十分となり,O(1)の質問が必要となる.
一方,STアルゴリズムはO(nlogn)時間内に前処理を行い,O(1)時間内に各クエリに答えることができ,実際には動的計画とテーブル打ちの考え方である.
1.原理
1)前処理
O(1)で区間の最値を求めるには,動的プランニング処理の手法を用いて,dp[i][j]で区間[i,j]の最大値を記録することが自然な考え方であり,これは明らかに状態遷移方程式:dp[i][j]=max(dp[i][j-1],a[j])があるが,このような前処理はO(n*n)であり,さらに最適化できる.
max関数は、許容区間オーバーラップ、すなわちmax(i,j,k)=max(max(i,j),max(j,k))を満たす.すなわち、2つの小さなオーバーラップ区間から、直接1つの大きな区間を押し出すことで、メンテナンスの区間数を減らすことができる.
倍増の思想を用いて,A[i]を区間最値を要求する数列とし,F[i,j]はi番目の数から2^j番目の数の中で最大値を表す.(DPの状態)
F[i,0]=A[i](DPの初期値)がわかる
F[i,j]を平均して2つのセグメント(F[i,j]は必ず偶数の数字)に分け、iからi+2^(j-1)-1までを1セグメント、i+2^(j-1)からi+2^j-1までを1セグメント、長さはいずれも2^(j-1)
すると、F[i,j]=max(F[i,j-1],F[i+2^(j-1),j-1])が得られる(状態遷移方程式)
例:
A:3 2 4 5 6 8
F[1,0]は1番目の数から、長さが2^0=1の最大値を表し、実は3
F[1,1] = max(3,2) = 3
F[1,2] = max(3,2,4,5) = 5
F[1,3] = max(3,2,4,5,6,8,1,2) = 8
2)照会
クエリーする区間を(i,j)とすると、この閉区間[i,j]をカバーする最小べき乗を見つける必要があり、区間長はj-i+1であるため、k=log 2(j-i+1)を取ることができる.RMQ(i,j)=max{F[i,k],F[j-2^k+1,k]}
例:要求区間[1,5]の最大値
あります:k=log 2(5-1+1)=2
則:RMQ(1,5)=max(F[1,2],F[5-2^2+1,2])=max(F[1,2],F[2,2])
2.実現

int dpMax[N][20];
int dpMin[N][20];
int a[N];
void initMax(int n){//        
    for(int i=1;i<=n;i++)
        dpMax[i][0]=a[i];
    for(int j=1;(1<

【2次元RMQ】
1次元RMQ問題は1つの数列Aの中の最も値を求めるので、2次元RMQ問題は1つのn*mの行列の中で、あるサブ行列の内の最も値を求めるのです
1.原理
1)初期化
F[i][j][ii][jj]=x表示を(i,j)を左上隅とし、(i+(1<(DPの状態)
分かりやすい:F[i][j][0][0]=G[i][j](DPの初期値)
F[i][j][ii][jj]のiiが0でないと仮定すると、F[i][j][ii][jj]=max(F[i][j][ii-1][jj]、F[i+(1<(状態遷移方程式)
iiが0であればjjで求める、すなわちF[i][j][ii][jj]=max(F[i][j][ii][jj-1]、F[i][j+(1<(状態遷移方程式)
簡単に言えば、2 D問題を1 D問題解に変換することです.
2)照会
(x 1,y 1)を左上隅、(x 2,y 2)を右下角とする矩形について、これを4つの小さなブロックに分け、この4つの小さなブロックには重なり合う部分があるかもしれないが、彼らは共通して目標矩形を構成している.

F[x1][y1][ii][jj]

F[x1][y2-(1<

F[x2-(1<

F[x2-(1<

それでは、まず第1、2の小さい塊の最値を解くことができて、第3、4の小さい塊の最値、最後に更に全体の最値を求めます
次のようになります.

temp1 = max(F[x1][y1][ii][jj] , F[x1][y2-(1<

temp2 = max(F[x2-(1<

最終結果:res=max(temp 1,temp 2)
2.実現

int G[N][N];
int dpMin[N][N][10][10];
int dpMax[N][N][10][10];
void initRMQ(int n,int m){// n*m      RMQ      1  

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            dpMin[i][j][0][0]=dpMax[i][j][0][0]=G[i][j];

    for(int ii=0;(1<

【例題】

Find the hotel(HDU-3193)(1次元RMQ):ここをクリック

Check Corners(HDU-2888)(2次元RMQ):ここをクリック

バランスのとれたラインナップ(洛谷-P 2880)(RMQは極差を求める):ここをクリックして同題:Balanced Lineup(POJ-3264):ここをクリックして

A Magic Lamp(HDU-3183)(RMQ+シミュレーション):ここをクリック