ツリーを配列に線形化し、パス上の "sum"クエリに応答する

Question

問題はコーデックのtravtree問題によって動機付けられます。 editorialでは、各ノードの検出と終了時間をDFSトラバーサルで記録することによって、ツリーを配列に線形化することを推奨しています。今すぐ、そのノードの[discovery time, exit time]セグメントで発生したイベントを合計することで、sum subtreeに関する質問に素早く答えることができます。 （私たちはFenwickツリーを使ってこれらのクエリに素早く答える）。

この問題を解決するには、sum pathの質問にすばやく答える必要があります。つまり、a, bの最短経路で発生したイベントを合計します。そんなことがあるものか？

update(BT2,event_node,1); 
    update(BT2,out[event_node],-1); 

とsum path(a,b)は今、このです：queryプレフィックス合計です

int l = lca(a,b); 
    ans = query(BT2,a) + query(BT2,b) - query(BT2,l) - (l==1 ? 0 : query(BT2, parent[0][l])); 

。彼らはこれを更新するごとに興味深いイベントについて

：彼らは与える答えはこれですそれはどうやって正しいですか？接頭辞の和をaまで見ると、lとaの間のパスとは無関係の多くのノードが発生する可能性があります。

イベントがノードvに起こる、我々update(IN[v], 1)とupdate(OUT[v], -1)：私たちは確かに次の操作を実行する必要があるツリーノード間の最短経路a, bに起こった出来事の合計 - sum pathクエリを線形化するために

Answer 1

。 INはノードのDFS discovery timeおよびOUTであり、DFS exit timeです。

ここでクエリはquery(IN[b]) - query(IN[a]-1)になります。 query(IN[b])はプレフィックスの合計です。ルートから始まり、bに達するまでツリーをトラバースします。各ノードvの場合、直接ルートにないをルートからbに渡すことになるので、それを発見して最終的に終了します。ノードの場合、が見つかり、ではなく、が終了します。更新された方法のため、これはパスroot, b（bを含む）のノードを効果的に合計することを意味します。

query(IN[a]-1)で同じことが起こったことが明らかになりました - これはパスroot, aのノードの合計です（今度はaは含まれません）。それらを引くとa, bとなります。スケッチを描くと、あなた自身のためにそれを見るでしょう。完全を期すため

---

からsum subtree方法はupdateおよびqueryの両方において異なっています。各イベントについては、update(IN[v])のみです。今度はsum subtree(a)を照会するために、query(OUT[a]) - query(IN[a]-1)を実行します。今度はquery(OUT[a])で、aを発見してから、aのすべてのノードを終了するまで、すべてのノードを合計します。ここで、が発見されるまで、query(IN[a] - 1) - すべてのノードを引く。我々はちょうどaサブツリーだけを残しています。