等级祖先问题

在大学的算法课程中,向我介绍了竞争编程中各种基于图的算法。 最受欢迎的方法之一是“重轻分解”。 最初,很难掌握算法的所有细节,但是到我研究所有复杂性时,我就可以猜出其流行的原因。

该算法在基于查询的问题中有很多应用,并且实际上是解决基于树的查询的最有效算法之一。 在这里,我不会详细介绍算法,而是尝试介绍我在互联网上找到的HLD应用程序。 该问题称为“级别祖先问题”,并表示为动态树上的查询问题。 要查询的树可以是任何形状,并且可以有很多孩子。

级别祖先查询LA(u; d)请求节点u的深度d祖先。 然后,将给定的N个节点以树T为根,将级别祖先问题简化为预处理,以支持任意数量的级别祖先查询。 必须同时优化预处理时间和查询时间

我们给了一个静态的根树,可以对其进行预处理。 然后,给级别祖先查询一个节点V和一个数l,并且必须找到V的第l个祖先。这等效于找到v的depth-d祖先,其中d + l = depth(V) 。

背景

现在,在我们讨论水平祖先问题的解决方案之前,将是什么样子! 我想强调HLD的关键功能,这些功能将帮助您了解解决方案。

术语

  • 特殊子节点在节点的所有子节点中,具有最大子树大小的子节点被视为特殊子节点。 每个非叶节点都只有一个特殊子节点。
  • 特殊边缘:对于每个非叶节点,将节点与其特殊子节点相连的边缘视为特殊边缘

HLD

在“重光分解”中,我们将树分成顶点不相交的链 (这意味着没有两个链具有相同的节点),这样,从树中的任何节点移动到根节点,我们最多都必须进行更改 log(N)链。 换句话说,从任何节点的路径都可以分成几部分,使得每一部分仅属于一个链,那么我们将只有log(N)个部分。

我们知道,使用段树可以用O(log N)复杂度回答每个链中的查询,并且每个路径最多需要考虑log N个链。 因此,总的来说,我们为树查询提供了O(log²N)复杂度解决方案。

现在这是一个事实,证明大量的光分解将树分解为对数N个片段:

  • 考虑一个节点X,其子树大小为s,并具有m个子节点。
  • 特殊子树可能的最小子树大小是ceil(s / m) 。 这就是说,正常儿童的最大尺寸为ceil(s / m)m> 2。
  • 更改链意味着我们正在从节点移动到正常子节点,因此每次更改链时,我们至少将子树的大小减半。 对于大小为N的树,我们最多可以将其对分N次。

现在,该解决方案非常简单,如果仔细查看了HLD的所有细节,您可能会自己猜对了!

在解决方案中,我们从给定的节点开始,然后向后移动到与查询中指定的深度相等的长度。 我们必须小心这一事实,即通往根的路径应该是最优的,这样即使在路径的单个点上,我们也不会访问会增加与根的距离的节点。

现在,按照将树划分为链的方式,我们可以保存当前节点的父节点,并对此进行O(1)查询。 同样,在链中,我们向指定索引的移动是O(1)。 因此,我们检查了链中父级的索引,并将其与提供给我们的深度进行比较。 之后,我们有以下选择:

  • 索引>深度。 在这种情况下,我们以当前链中的index = depth进行移动,这使我们的祖先达到了给我们的深度。
  • 如果index == depth,我们的父链就是我们要寻找的祖先
  • 如果index <depth,我们通过depth-index更新深度,并使连接当前链和当前链的父链的节点成为当前节点,并对其进行递归操作,直到我们的index == depth。

https://bitbucket.org/snippets/vaibha9518/bBxB/level-ancestor-problem-solution