RMQ問題
2598 ワード
RMQ(range) minimum/maximum queryは、照会区間の最大最小値です.
区間の最大最小値を求めるには、O(n)時間の複雑度を計算するアルゴリズムが自然に思いつきますが、問い合わせが多い場合は?これは必ずタイムアウトします.もちろん、私たちは線分樹で解くことができます.毎回のクエリの時間をlog(n)に下げることができますが、RMQアルゴリズムについては、前処理をしたら、後での問い合わせにはO(1)の時間しかかかりません.SparseTableアルゴリズムはRMQ問題を解決するためのより良いアルゴリズムです.オンラインアルゴリズムに属しています.
オンラインアルゴリズム:コンピュータ科学において、オンラインアルゴリズムとは、プログレッシブな方法で入力を一つ一つ処理することができるということです.つまり、最初にすべての入力を知る必要はありません.
オフラインアルゴリズム:問題のすべての入力データを知る必要があります.問題を解決したらすぐに結果を出力します.例えば、並べ替えを選択する前に、並べ替え要素のすべてを知る必要がありますが、並べ替えを挿入する必要はありません.
簡単にオンラインアルゴリズムをまとめますと、プログラムは先に前処理をして、その後の照会に対して、すぐに答えられます.オフラインのアルゴリズムはあなたが先に必要なことをプログラムに教えてください.彼は一回で解決します.
はい、次はスピリッツを説明します.テーブルアルゴリズム
1.最も価値のある配列を求める
SparseTableアルゴリズムの前処理は動的計画の思想である.
配列maxn[i]、[j]は、与えられた配列が下付きiから始まり、長さは2^jの区間最大値(最小値は同じ)であるarr[i]----arr[i+2^j-1]という区間の最大値を表します.
そこで私たちはこのような動的移動方程式のmaxn[i][j]=max(maxn[i]、[j-1],maxn[i+2^(j-1)][j-1]を書き出して読めますか?
実は区間【i,i+2^j-1】を2つに分けて、1つは【i,i+2^(j-1)-1】と【i+2^(j-1)、i+2^j】です.
maxn[i][j]については、jが0に等しく、つまり、区間長が1の最大値は、明らかにmaxn[i]、[0]=arr[i]である.
これで私達はSparseを書くことができます.テーブルの前処理部分です.
区間の長さが2の場合は、まず区間の長さを1として求めますか? たとえば区間[1,2]は区間[1,1]だけです. [2,2]の中で一番の値を取ると4の長さは必ず先に2の長さを算出します.例えば、区間[6,9]の一番の値を求めるなら、区間[6,7]、[8,9]の中で一番の値を取ればいいです....
だから一番外側の循環は区間の長さに違いないです.中のサイクルは全部分かりますよね.
2.クエリー
この一番値の区間の配列を求めました.次は検索です.
例えば、区間[a,b]の一番の値を調べます. どうやって求めますか
私たちの一番値の配列は全部区間長が2^k(k=0,1,2,3...)であることに気づきました.
ですから、区間[a,b]は必ず二つの区間に分けます.長さは2^xです. 2^yの区間は直接に私達が得た一番値の配列を利用して一番値を求めることができますか?
ここには二つの未知数があります.直接にkを取ります.kに対してa+2^k-1=bを満足します. k=log 2(b-a+1)(ここではa+2^k=bではないかと注意してください.常に2^kは区間の要素の個数です.)区間a,bの最大値はmax(maxn[a]、[k],maxn[b-2^k+1][k])ではなく、区間の長さに対して4のlogs=2を保証します.しかし、これは大丈夫です.例えば、区間の長さが5の【3,7】に対して、私達はlog 2(7-3＋1)を2つに整理しました.
max(【3,6】、【4,7】)は、max関数のうちの前のmaxn[a]、[k]が私たちの求めている最も価値のある区間をaで始まり、後ろのmaxn[b-2^k+1][k]が必ずbで終わることを保証しています.
区間の最大最小値を求めるには、O(n)時間の複雑度を計算するアルゴリズムが自然に思いつきますが、問い合わせが多い場合は?これは必ずタイムアウトします.もちろん、私たちは線分樹で解くことができます.毎回のクエリの時間をlog(n)に下げることができますが、RMQアルゴリズムについては、前処理をしたら、後での問い合わせにはO(1)の時間しかかかりません.SparseTableアルゴリズムはRMQ問題を解決するためのより良いアルゴリズムです.オンラインアルゴリズムに属しています.
オンラインアルゴリズム:コンピュータ科学において、オンラインアルゴリズムとは、プログレッシブな方法で入力を一つ一つ処理することができるということです.つまり、最初にすべての入力を知る必要はありません.
オフラインアルゴリズム:問題のすべての入力データを知る必要があります.問題を解決したらすぐに結果を出力します.例えば、並べ替えを選択する前に、並べ替え要素のすべてを知る必要がありますが、並べ替えを挿入する必要はありません.
簡単にオンラインアルゴリズムをまとめますと、プログラムは先に前処理をして、その後の照会に対して、すぐに答えられます.オフラインのアルゴリズムはあなたが先に必要なことをプログラムに教えてください.彼は一回で解決します.
はい、次はスピリッツを説明します.テーブルアルゴリズム
1.最も価値のある配列を求める
SparseTableアルゴリズムの前処理は動的計画の思想である.
配列maxn[i]、[j]は、与えられた配列が下付きiから始まり、長さは2^jの区間最大値(最小値は同じ)であるarr[i]----arr[i+2^j-1]という区間の最大値を表します.
そこで私たちはこのような動的移動方程式のmaxn[i][j]=max(maxn[i]、[j-1],maxn[i+2^(j-1)][j-1]を書き出して読めますか?
実は区間【i,i+2^j-1】を2つに分けて、1つは【i,i+2^(j-1)-1】と【i+2^(j-1)、i+2^j】です.
maxn[i][j]については、jが0に等しく、つまり、区間長が1の最大値は、明らかにmaxn[i]、[0]=arr[i]である.
これで私達はSparseを書くことができます.テーブルの前処理部分です.
void getbestarr(int n)//n
{
int tem = (int)floor(log2((double)n));// 2^tem==n
for(int i=1;i<=n;i++)
minn[i][0]= maxn[i][0] = arr[i];
for(int j=1;j<=tem;j++) // 1
for(int i=1;i+(1<<j)-1<=n;i++)
{
maxn[i][j] = max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1]); //
minn[i][j] = min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]); //
}
}区間の長さが2の場合は、まず区間の長さを1として求めますか? たとえば区間[1,2]は区間[1,1]だけです. [2,2]の中で一番の値を取ると4の長さは必ず先に2の長さを算出します.例えば、区間[6,9]の一番の値を求めるなら、区間[6,7]、[8,9]の中で一番の値を取ればいいです....
だから一番外側の循環は区間の長さに違いないです.中のサイクルは全部分かりますよね.
2.クエリー
この一番値の区間の配列を求めました.次は検索です.
例えば、区間[a,b]の一番の値を調べます. どうやって求めますか
私たちの一番値の配列は全部区間長が2^k(k=0,1,2,3...)であることに気づきました.
ですから、区間[a,b]は必ず二つの区間に分けます.長さは2^xです. 2^yの区間は直接に私達が得た一番値の配列を利用して一番値を求めることができますか?
ここには二つの未知数があります.直接にkを取ります.kに対してa+2^k-1=bを満足します. k=log 2(b-a+1)(ここではa+2^k=bではないかと注意してください.常に2^kは区間の要素の個数です.)区間a,bの最大値はmax(maxn[a]、[k],maxn[b-2^k+1][k])ではなく、区間の長さに対して4のlogs=2を保証します.しかし、これは大丈夫です.例えば、区間の長さが5の【3,7】に対して、私達はlog 2(7-3＋1)を2つに整理しました.
max(【3,6】、【4,7】)は、max関数のうちの前のmaxn[a]、[k]が私たちの求めている最も価値のある区間をaで始まり、後ろのmaxn[b-2^k+1][k]が必ずbで終わることを保証しています.
int query(int a,int b,bool getwhat)//getwhat
{
int k = log2(b-a+1);
if(getwhat)
return max(maxn[a][k],maxn[b-(1<<k)+1][k]);
else
return min(minn[a][k],minn[b-(1<<k)+1][k]);
}