將樹線性化爲數組並回答路徑上的「求和」查詢

Question

問題出在codechef中的travtree問題。在editorial，他們建議通過記錄每個節點在DFS遍歷中的發現和退出時間，將樹線性化到數組。現在我們可以快速回答有關sum subtree的查詢 - 通過對該節點的[discovery time, exit time]段中發生的事件進行求和。 （我們使用Fenwick樹來快速回答這些查詢）。

然而，要解決這個問題，我們還需要快速回答sum path查詢。那就是 - 在a, b之間的最短路徑上發生的事件總和。這怎麼可能？他們給出的答案是這樣的：

因爲他們更新這個每個有趣的事件：

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

和sum path(a,b)現在是這樣的：

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

哪裏query是前綴總和。這是怎麼回事？當您查看前綴總和直到a時，您可能會遇到很多與l和a之間的路徑無關的節點！

Answer 1

爲了線性化sum path查詢 - 所發生樹節點a, b之間的最短路徑上活動的總和，我們確實必須做到以下幾點：

當一個事件節點v情況下，我們update(IN[v], 1)和update(OUT[v], -1)。節點的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。我們只剩下a子樹。