rmq問題--stアルゴリズム
9966 ワード
回転:http://blog.csdn.net/niushuai666/article/details/6624672
1.概要
RMQ(Range Minimm/Maximum Query)とは、区間の最値クエリーであり、長さnの数列Aに対して、若干の質問RMQ(A,i,j)(i,j<=n)を答え、数列Aにおいてi,jの最小／大値を下付きで返す問題である.この二つの問題は実際の応用においてよくある問題です.この二つの問題を解決するための比較的効率的なアルゴリズムを紹介します.もちろん、この問題は線分樹(区間樹ともいう)でも解決できます.アルゴリズムの複雑度はO(N)～O(logN)です.ここでは紹介しません.
2.RMQアルゴリズム
この問題に対して最も容易に考えられる解は遍歴的であり,複雑さはO(n)である.しかし、データ量が非常に大きく、頻繁に検索されている場合、アルゴリズムは有効な時間で正解を確認することができない.
本セクションでは、より効率的なオンラインアルゴリズム(STアルゴリズム)によるこの問題の解決を紹介します.オンラインアルゴリズムとは、ユーザーがクエリーを入力するごとにすぐにクエリーを処理することです.このアルゴリズムは一般的に比較的長い時間で前処理を行い、十分な情報があれば、少ない時間で各クエリに答えられます.ST(Sparse Table)アルゴリズムは非常に有名なオンラインRMQ問題を処理するアルゴリズムであり、O(nlogn)時間内に前処理を行い、O(1)時間内に各クエリに回答することができます.
(一)まず前処理を行い、動的計画(DP)で解決する.
A[i]を設定すると、区間の一番値が要求される数列であり、F[i,j]はi番目の数から連続して2^j個の数の中の最大値を表します.(DPの状態)
たとえば:
Aの数列は、3 2 4 5 6 8 1 2 9 7です.
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;
そして、F[i,0]はA[i]に等しいということが分かります.(DPの初期値)
このようにDPの状態、初期値はすでにあり、残りは状態移行方程式である.
私たちはF[i,j]を平均的に2つのセグメントに分けます(f[i,j]は偶数の数字に違いないので)、iからi+2^(j-1)-1は一段で、i+2^(j-1)からi+2^j-1までは一段です(長さは全部2^(j-1))).上記の例を用いて、i=1,j=3の場合、3,2,4,5と6,8,1,2の2つの部分を説明します.F[i,j]はこの2つのセグメントのそれぞれの最大値の中の最大値である.そこで、状態移行方程式F［i,j］＝max(F［i,j−1］,F［i＋2^(j−1),j−1］を得た.
コードは以下の通りです
void RMQ(int num //前処理->O(nlogn){ for(int j = 1; j < 20; ++j) for(int i = 1; i <= num ++i) if(i + (1 << j) - 1 <= num { maxsum[i][j] = max(maxsum[i][j - 1) maxsum[i + (1 << (j - 1)」[j - 1); minsum[i][j] = minsum[i][j - 1) minsum[i + (1 << (j - 1)」[j - 1); } ｝ ここで注意したいのは循環の順序であり、外層はjであり、内層のiであることが分かります.なぜでしょうか?iは外にあり、jは中にありますか?
答えはだめです.この状態の方程式の意味を理解する必要があるからです.
状態遷移方程式の意味は、全ての長さがF［i,0］である1つの要素を更新し、2つの1つの要素の最値を通して、全ての長さがF［i,1］である2つの要素の最値を取得し、その後、2つの2つの要素の最値を通して、F［i,2］である4つの要素の最値を獲得し、これらをすべての長さの最値に更新することである.
i以外の場合、jを含めて更新する順序はF[1,0],F[1,1],F[1,2],F[1,3],更新が1から1要素,2要素,4要素,8要素(A[0],A[1],....A[7])の一番の値を表します.ここでF[1,3]=max(A)[1,A,[4][A,A,A][1,A,[4],[A,A,[4],[1][A,A,A,1],[1,A,A,[5,A,A,A,A,A,A,A,1],[4[1],[1],[1,A,A,A,A,A,A,A,A,A,私たちはmax(A[0],A[1],A[2],A[3])とmax(A[4],A[5]を計算していません.A[6],A[7])ですから、このような方法は間違いです.
このようなエラーを避けるためには、この状態遷移方程式に代表される意味をよく理解しなければならない.
(二)そして照会です.
もし私たちが照会したい区間が(i,j)であれば、この閉塞区間(左境界がiを取り、右境界がjを取る)をカバーする最小べき乗を見つける必要があります.
この区間の長さはj-i+1ですので、k=log 2(j-i+1)を取ります.RMQ(A,i,j)=max｛F[i,k],F[j-2^k+1,k]｝があります.
例えば、要求区間[2,8]の最大値、k=log 2(8-2+1)=2、すなわちmax(F[2,2],F[8-2^2+1,2]= max(F[2,2],F[5,2])
ここでは、「演算子と＋演算子の優先度」という点にも注意が必要です.
例えばこの表式:5-1<<2はいくらですか?
4*2*2=16です.だから、5-(1<<2)と書くべきです.5-1*2*2=1です.
私のモデル:
1.概要
RMQ(Range Minimm/Maximum Query)とは、区間の最値クエリーであり、長さnの数列Aに対して、若干の質問RMQ(A,i,j)(i,j<=n)を答え、数列Aにおいてi,jの最小／大値を下付きで返す問題である.この二つの問題は実際の応用においてよくある問題です.この二つの問題を解決するための比較的効率的なアルゴリズムを紹介します.もちろん、この問題は線分樹(区間樹ともいう)でも解決できます.アルゴリズムの複雑度はO(N)～O(logN)です.ここでは紹介しません.
2.RMQアルゴリズム
この問題に対して最も容易に考えられる解は遍歴的であり,複雑さはO(n)である.しかし、データ量が非常に大きく、頻繁に検索されている場合、アルゴリズムは有効な時間で正解を確認することができない.
本セクションでは、より効率的なオンラインアルゴリズム(STアルゴリズム)によるこの問題の解決を紹介します.オンラインアルゴリズムとは、ユーザーがクエリーを入力するごとにすぐにクエリーを処理することです.このアルゴリズムは一般的に比較的長い時間で前処理を行い、十分な情報があれば、少ない時間で各クエリに答えられます.ST(Sparse Table)アルゴリズムは非常に有名なオンラインRMQ問題を処理するアルゴリズムであり、O(nlogn)時間内に前処理を行い、O(1)時間内に各クエリに回答することができます.
(一)まず前処理を行い、動的計画(DP)で解決する.
A[i]を設定すると、区間の一番値が要求される数列であり、F[i,j]はi番目の数から連続して2^j個の数の中の最大値を表します.(DPの状態)
たとえば:
Aの数列は、3 2 4 5 6 8 1 2 9 7です.
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;
そして、F[i,0]はA[i]に等しいということが分かります.(DPの初期値)
このようにDPの状態、初期値はすでにあり、残りは状態移行方程式である.
私たちはF[i,j]を平均的に2つのセグメントに分けます(f[i,j]は偶数の数字に違いないので)、iからi+2^(j-1)-1は一段で、i+2^(j-1)からi+2^j-1までは一段です(長さは全部2^(j-1))).上記の例を用いて、i=1,j=3の場合、3,2,4,5と6,8,1,2の2つの部分を説明します.F[i,j]はこの2つのセグメントのそれぞれの最大値の中の最大値である.そこで、状態移行方程式F［i,j］＝max(F［i,j−1］,F［i＋2^(j−1),j−1］を得た.
コードは以下の通りです
void RMQ(int num //前処理->O(nlogn)
答えはだめです.この状態の方程式の意味を理解する必要があるからです.
状態遷移方程式の意味は、全ての長さがF［i,0］である1つの要素を更新し、2つの1つの要素の最値を通して、全ての長さがF［i,1］である2つの要素の最値を取得し、その後、2つの2つの要素の最値を通して、F［i,2］である4つの要素の最値を獲得し、これらをすべての長さの最値に更新することである.
i以外の場合、jを含めて更新する順序はF[1,0],F[1,1],F[1,2],F[1,3],更新が1から1要素,2要素,4要素,8要素(A[0],A[1],....A[7])の一番の値を表します.ここでF[1,3]=max(A)[1,A,[4][A,A,A][1,A,[4],[A,A,[4],[1][A,A,A,1],[1,A,A,[5,A,A,A,A,A,A,A,1],[4[1],[1],[1,A,A,A,A,A,A,A,A,A,私たちはmax(A[0],A[1],A[2],A[3])とmax(A[4],A[5]を計算していません.A[6],A[7])ですから、このような方法は間違いです.
このようなエラーを避けるためには、この状態遷移方程式に代表される意味をよく理解しなければならない.
(二)そして照会です.
もし私たちが照会したい区間が(i,j)であれば、この閉塞区間(左境界がiを取り、右境界がjを取る)をカバーする最小べき乗を見つける必要があります.
この区間の長さはj-i+1ですので、k=log 2(j-i+1)を取ります.RMQ(A,i,j)=max｛F[i,k],F[j-2^k+1,k]｝があります.
例えば、要求区間[2,8]の最大値、k=log 2(8-2+1)=2、すなわちmax(F[2,2],F[8-2^2+1,2]= max(F[2,2],F[5,2])
ここでは、「演算子と＋演算子の優先度」という点にも注意が必要です.
例えばこの表式:5-1<<2はいくらですか?
4*2*2=16です.だから、5-(1<<2)と書くべきです.5-1*2*2=1です.
私のモデル:
1 //poj 3264
2 #include <iostream>
3 #include <cstdio>
4 #include <cmath>
5 #include <algorithm>
6
7 using namespace std;
8
9 #define MAXN 50010
10 #define Max(x,y) (x>y?x:y)
11 #define Min(x,y) (x>y?y:x)
12
13 int maxsum[MAXN][20],minsum[MAXN][20];// i 2^j /
14
15 void RMQ(int num)
16 {
17 for(int j=1;j<20;j++)
18 for(int i=1;i<=num;i++)
19 {
20 if(i+(1<<j)-1 <= num)
21 {
22 maxsum[i][j]=Max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]);
23 minsum[i][j]=Min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]);
24 }
25 }
26 }
27
28 int main()
29 {
30 int i,j,num,t,query;
31 while(scanf("%d%d",&num,&query) != EOF)
32 {
33 for(i=1;i<=num;i++)
34 {
35 scanf("%d",&maxsum[i][0]);
36 minsum[i][0]=maxsum[i][0];
37 }
38 RMQ(num);
39 int st,en,maxl,minl;
40 while(query--)
41 {
42 scanf("%d%d",&st,&en);
43 int k=(int)((log(en-st+1))/log(2.0));
44 maxl=Max(maxsum[st][k],maxsum[en-(1<<k)+1][k]);
45 minl=Min(minsum[st][k],minsum[en-(1<<k)+1][k]);
46 printf("%d
",maxl-minl);
47 }
48 }
49 return 0;
50 }