O(n log n) 時間で配列 A を前処理して、findmax(i,j) の形式のクエリに応答できるようにします。j] (つまり、O(1) の配列要素 A[i]、A[i + 1]、...、A[j]) の最大値) クエリあたりの時間。
追加の質問: 上記のクエリに O(log n) 時間で回答できるように、O(n) 時間で前処理する方法を示してください。
質問する
399 次
1 に答える
2
この問題は、範囲の最小 (最大) クエリ - RMQとして知られています。リンクは基本的にあなたの両方の質問に答えます。
古典的な解決策は、動的プログラミングとセグメント ツリーです。
于 2013-02-24T19:39:52.087 に答える