データ構造コースでテストを受けましたが、質問の 1 つは次のとおりでした。
o(1) の複雑さで配列内の 2 つの数値の間の最小値を与える範囲最小クエリで維持される n サイズの配列があるとします。もちろん、配列はさまざまなオプションの動的計画法を使用して RMQ に応答するように準備された o(n) でした。問題は、配列内の 1 つのオブジェクト (数値) を変更した場合、o(1) で RMQ を見つけることができるようにするために行った準備をどのように変更すればよいか、そしてそれにはどのような複雑さが必要かということです。
答えは、o(n) で新しい RMQ を作成することではありません。それより小さくする必要があります。
この問題は宿題ではありません。理解するためにテストをやりたいだけです。
前もって感謝します。