一定の時間で最小要素を取得する

Question

私は、サイズ0の配列Aを持っているとします。ここで、0 < = A [i] < = nです。

私は2つのフォワード配列や後方、サイズn、考えてみましょう：私の質問がある

Forward[i] = index j where 
       A[j] = min(A[i], A[i+1], ..., A[n-1]) 

と

Backward[i] = index j where 
       A[j] = min(A[i], A[i-1], ..., A[0]) 

：A、前方および後方与え

• を
• 与えられた2つのインデックスlとR

Iは、一定の時間でインデックスkは、[K] =分（[L]、A [L + 1]、...、A [R]）ことを発見することができ？

Answer 1

No.少なくともO（1）時間ではありません。カウンタの例は次のとおりです。 0-basedインデックス作成がここで使用されます。私は範囲[3, 7]の最小値のインデックスを取得するように依頼する場合は、あなたがそれをどのように行うだろう、今

index  = {0, 1, 2, 3, 4, 5, 6, 7, 8} 
A   = {1, 3, 5, 7, 9, 6, 4, 2, 0} 

Forward = {8, 8, 8, 8, 8, 8, 8, 8, 8} 
Backward = {0, 0, 0, 0, 0, 0, 0, 0, 8} 

してみましょうか？

基本的には、範囲内に見つけることが役に立たないであろう[B]

forward[a] > bとbackward[b] < a場合。

Answer 2

いいえ、できません。カウンタの例を示します。その場合には役に立たないとあなたがO(k-l)である配列を検索する必要が

A  = {0, 4, 3, 2, 3, 4, 0} 
Forward = {6, 6, 6, 6, 6, 6, 6} 
Backward = {0, 0, 0, 0, 0, 0, 0} 
l = 1, k = 5 

Forward IEとBackward。