ツリー上のパスでクエリに答えるには？

Question

私は配列を持っていて、インデックスiからjまでのすべての要素の合計を見つけるようなクエリに答える必要があります。ノードiからjへのパスに対してこのようなクエリに答えるのと同じように、 iからjまで存在する唯一の経路）。

LCA私はそれを線形配列に分解してセグメントツリーを使用する範囲最小クエリを使用して検索する方法を知っていますが、サムクエリに対しては変更できません。それ、どうやったら出来るの？

Answer 1

これは処理の要件によって異なります。複雑さの制限がありますか、または昼食時に作業可能で保守可能なコードを持つことが目標ですか？

それは後者だ場合は、シンプルなアプローチを取る：

• は、ツリー内の両方のノードを検索します。
• 最初のノードからルートにトラバースし、パスコストを合計し、各ノードで部分和を維持します。
• 2番目のノードから、ルートに向かってトラバース・アンド・サム（全合計のみ、部分なし）も開始します。
• 最初のノードの祖先であるノードに遭遇すると、LCAが見つかりました。
• 現在の合計を、LCAの最初のノードの部分合計に加算します。完了しました。

このアルゴリズムは、第1期のデータ構造の学生が容易に理解できます。 LCAの一貫性チェックでは、O（log（n）^ 2） - 悪くはないが、LCAの線形事前作業と一定時間問合せリターンの最適化はできません。

---

あなたが速いアルゴリズムが必要な場合は、その後、私は、各ノードはまた、その先祖の各部分和のハッシュされたリスト（例えばPython辞書）を計算するようにあなたはLCA事前作業アルゴリズムを強化することを示唆しています。これを済ませれば、LCAの一定時間計算と各部分合計の一定時間ルックアップが得られます。