データ構造コースでテストを受けましたが、質問の 1 つは次のとおりでした。
o(1) の複雑さで配列内の 2 つの数値の間の最小値を与える範囲最小クエリで維持される n サイズの配列があるとします。もちろん、配列はさまざまなオプションの動的計画法を使用して RMQ に応答するように準備された o(n) でした。問題は、配列内の 1 つのオブジェクト (数値) を変更した場合、o(1) で RMQ を見つけることができるようにするために行った準備をどのように変更すればよいか、そしてそれにはどのような複雑さが必要かということです。
答えは、o(n) で新しい RMQ を作成することではありません。それより小さくする必要があります。
この問題は宿題ではありません。理解するためにテストをやりたいだけです。
前もって感謝します。
変更された要素のインデックス I と新しい値 V を格納します。
クエリ [L,R] を取得すると、L <= I <= R かどうかを確認し、そうであれば old_rmq(L,R) と V の最小値を返します。
RMQと の複雑さに基づいて、実際には には 3 つのタイプのアルゴリズムがありupdateますquery。
Update Query
1. O(N) O(1)
2. O(1) O(N)
3. O(logN) O(logN)
1 番目と 2 番目のタイプのアルゴリズムは、実装が非常に簡単です。1 つ目は、考えられるすべてのクエリの値を格納し、O(1)時間内にそれらに応答することです。2 つ目は、データ構造を時間内に更新するだけですO(1)が、クエリには時間がかかりますO(N)。あなたの質問によると、あなたのような組み合わせを持つことは不可能です。
ただし、3 番目のタイプのアルゴリズムは特に興味深いものです。O(logN)ではなく、クエリに時間がかかるという条件を緩和するO(1)と、更新やクエリの数に関係なく、全体の実行時間が一定になるという利点もあります。
私の知る限り、そのような実行時間を取得するために使用される最適なデータ構造は、セグメント ツリーとバイナリ インデックス ツリーです。