二分木を勉強中です！私はこの宿題に問題があります。この問題を解決するには、バイナリ ツリーを使用する必要があります。問題は次のとおりです。整数のリストが与えられます。次に、「A インデックスとインデックス B の間のリスト コンテンツの要素の最大値はいくつですか?」という形式のいくつかの質問に答える必要があります。例 ：
INPUT :
10
2 4 3 5 7 19 3 8 6 7
4
1 5
3 6
8 10
3 9
OUTPUT:
7
19
8
19
制限時間とメモリ (言語: C + +)
時間: 1 GHz マシンで 0.5 秒。メモリ: 16000 KB
制約
1 <= N <= 100000、ここで N はリスト内の要素の数です。
1 <= A、B <= N、ここで A、B は範囲の限界です。
1 <= I <= 10 000、ここで I は間隔の数です。
解決策をヒントだけにしないでください。本当にありがとう ！
コメントで既に説明したように、簡単にするために、配列にエントリを追加してサイズを 2 のべき乗にすることができます。これにより、バイナリ ツリーはすべての葉に対して同じ深さになります。実際のアルゴリズムではこれらの計算値を使用しないため、このリストに追加する要素は重要ではありません。
二分木では、ボトムアップ方式で最大値を計算する必要があります。これらの値は、これらのノードが表す範囲全体の最大値を示します。これがツリーの主要なアイデアです。
残っているのは、クエリをそのようなツリー ノードに分割することです。したがって、それらは、間隔のサイズよりも少ないノードを使用して元の間隔を表します。ツリー ノードが表す間隔の「パターン」を把握します。次に、入力間隔をできるだけ少数のノードに分割する方法を見つけます。単純な解決策から始めるかもしれません: 入力をリーブノード、つまり単一の要素に分割するだけです。次に、ツリーの内部ノードを使用して、間隔から複数の要素を「組み合わせる」方法を見つけます。ツリーを使用せずにこれを行うアルゴリズムを見つけてください(これには要素数の線形時間が必要ですが、ツリーの全体的な考え方は対数にすることです)。
配列は、この問題に最適なデータ構造です。
ただし、バイナリ ツリーを使用する必要がある場合は、(インデックス、値) をバイナリ ツリーに格納し、インデックスをキーにします。
サイズ 0 の間隔で動作するコードを書きます。これは非常に簡単です。
次に、サイズ 1 の間隔でいくつか書き込みます。それでも単純です。
次に、サイズ 2 の間隔でいくつか書き込みます。比較が必要になる場合があります。それはまだ簡単です。
次に、サイズ 3 の区間についていくつか書き込みます。サイズ 2 のどの区間を比較するかを選択する必要がある場合があります。これはあまり難しくありません。
これが完了したら、任意の間隔サイズで簡単に機能させることができます。