アルゴリズム コーディングの問題には、次の 2 種類の複数のクエリを評価する必要がある特定のクラスがあります。
- 一定範囲のデータに対して検索を実行する
- 特定の範囲のデータを更新する
私が最近取り組んでいる例の 1 つがこれです (ただし、これだけではありません): Quadrant Queries
ここで、アルゴリズムを最適化するために、1 つのアイデアがありました。動的プログラミングを使用して、特定の範囲の検索結果を保持し、必要に応じて他の範囲のデータを生成できます。
たとえば、インデックス 4 から 7 までの配列の数値の合計を計算する必要がある場合、4 までの要素の合計と 7 までの要素の合計を保持することができます。これは簡単で、2 つの差が必要になります。 + O(1) である 4 番目の要素。しかし、これは別の問題を引き起こします: 更新操作中に、更新された要素に続くすべての要素の保存された検索データを更新する必要があります。実際には試していませんが、これは効率が悪いようです。
誰かが、特別なデータ構造を使用して後続の更新操作を組み合わせることができると提案してくれました (実際にフォーラムで読んでください)。
質問: この種の問題を最適化する既知の方法はありますか? それを行う特別なデータ構造はありますか？私が言及したアイデア;直接アプローチよりも効率的である可能性はありますか? 試してみるべきですか？