首页 文章

将树线性化为数组并回答路径上的“sum”查询

提问于
浏览 次
1

问题是由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 是前缀和 . 怎么回事？当你查看前缀sum到 a 时，你可能会遇到许多与 l 和 a 之间的路径无关的节点！

algorithm tree fenwick-tree

1 回答

  • 0

    为了线性化 sum path 查询 - 在树节点之间的最短路径上发生的事件总数 a, b 我们确实必须执行以下操作：

    当节点 v 中发生事件时，我们 update(IN[v], 1) 和 update(OUT[v], -1) . IN 是节点的DFS discovery time 和 OUT DFS exit time .

    现在查询将是 query(IN[b]) - query(IN[a]-1) . query(IN[b]) 是前缀sum：它从根开始，遍历树，直到它到达 b . 请注意，对于每个节点 v ，我们将不会通过从root到 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 子树 .

    回复于

相关问题