n 個の値 x1、x2 ... xn のシーケンスが与えられ、次の形式の繰り返しクエリにすばやく答えようとしていると仮定します。 O(n log n) スペースで、O(log n) 時間でクエリに回答します。
O(n) space と O(log n) time を使用したデータ構造の解決策は知っていますが、O( n log n) space を使用する答えが必要です。
助言がありますか ？
O(n) 空間の解:
O(n) space : a1,a2,a3,...an の入力に対して、(a1,..,ak) の最小値と (ak+1,..,an) の最小値を含むノードを構築します。ここで、k = n/2。ツリーの残りの部分を再帰的に構築します。ここで、ai と aj の間の最小値を見つけたい場合: i,j の最小共通祖先を識別します。それを k とする i から始めて、k に到達するまで移動を続けます。子ノードが左ノードであったかどうかを反復ごとに確認します。はいの場合、右側のサブツリーの最小値を比較し、それに応じて現在の最小値を更新します。同様に、j については、それが正しいノードかどうかを確認します.... ノード k で、各サブツリーによって返された値を比較し、最小値を返します