C++ 中的重-轻分解

重轻分解 (Heavy-light decomposition, HLD) 是一种有价值的（且广为人知）的方法，常用于竞赛编程和算法构建中，用于优化树的查询。这是因为树本质上更难处理，尤其是在程序需要处理大量查询或修改时。最基本的测试，例如轴向查询，涉及沿着最少边数的两个节点之间值的求和、最大值或最小值查找，可能需要 O(n) 的时间，即线性算法，这在处理大型数据集或进行频繁查询时可能不总是适用的。

HLD 通过将树划分为重路径和轻边来改进这一点。其理念是以一种使查询时间为对数时间而不是线性时间的方式分割树。HLD 分析有助于将树分割成具有特定特征的片段，称为“重”边和“轻”边，这样就可以使用段树或 二进制索引树 (BIT) 等高效数据结构轻松方便地管理和更新跨越树段的操作。

HLD 在任何需要执行诸如处理节点之间路径查询或树分支等操作的问题中都很有用。例如，它可能用于 LCA、路径求和、范围查询或树结构中的动态更改等问题。换句话说，HLD 提供了一种组织树分解的优雅机制，限制了领域范围并提高了性能。

重轻分解的必要性

• 在基于树的问题中，最常见的任务之一是两个节点之间的查询。例如，可能需要对从树中节点 f 到节点 s 的各种位置存储在节点中的值进行求和或查找最大值。在基本实现中，要回答此类查询，需要从一个节点遍历到下一个节点，在最坏情况下（n 是树中的节点数）需要 O(n) 时间。这很耗时，尤其是在处理大型树或有多个查询时。
• 然而，树结构在节点和分支的结构方面已被证明具有固有的复杂性；层数可能很多，树的分支可能高度不平衡。这在设计高效的路径查询响应解决方案时带来了一些挑战。如果我们为每个查询构建一个更基础的系统，需要遍历树，那么我们将为每个查询进行大量重复计算，这将使大型输入的时空复杂度变得非常高。
• 这就是 HLD 发挥作用的地方。原因是当划分为重路径和轻边时，数据操作可以更有效地执行。理念是，树的大部分（对应于高密度边）将以连续的方式进行分段或路径化。最后，它使得沿着重路径的查询变得容易，而轻边则表示在这两条路径之间的切换。这使得可以使用段树等高效数据结构来在 O(log² n) 的时间内响应查询，而不是 O(n)。

重边和轻边

HLD 的核心概念围绕着将树的边划分为两种类型：重边和轻边。

重边

• 重边被定义为连接一个节点与其最大子树的边。子树的大小取决于子节点的数量加上一个（等于该节点本身）。本质上，目标是从起始节点开始，尽可能多地遍历最大的子树，直到创建一条重路径。这使得重路径包含树中尽可能多的节点，并限制查询期间路径之间的切换次数。
• 当我们向下遍历树并寻找重边时，我们保证了最大的子问题被组合在一起。它还使我们能够减少轻边的数量，这需要用户在路径之间切换。为了让这条重路径变得长而连续，我们可以轻松地处理沿着这条路径和查询的后续部分（假设为 n）的操作。

轻边

• 相对于某个节点，轻边是任何从该节点开始并延伸到或进入较小节点子树的边。每当我们遇到一条轻边时，就相当于离开了一条重路径并进入了另一条，但拆分的节点通常不容易区分。轻边代表了大型块的分割，树在此变得分支。这些轻边很重要，因为它们在两条重路径之间提供了过渡链接。
• HLD 的目标是尽量将轻边的数量保持在最低限度，因为它们在查询中需要进一步的过渡。因此，由于轻边会导致生成新的路径，如前所述，路径之间的切换会很困难。然而，假设一个小的世界概率水平，并且通过高效的分解，轻边的数量总是可以保持很小，以至于大多数查询总是可以在一些重路径内解决。

重轻分解如何工作？

似乎总有几个重要步骤用于在树上执行 HLD，如下所述。因此，当系统地执行这些步骤时，很容易将树分解为各种重路径段，可以使用智能策略轻松管理这些路径的路径查询。过程如下：

• 给树根
  健康控制点 (Health Locus of Control) 的过程始于给树根。这很重要，因为树通常是无根结构，并且查询可以在任何两个节点之间进行。如果树以任意节点（例如节点 0 或节点 1）为根，我们就给树一个方向。尽管简化了，但树根解决了计算下一步分解所需的子树的问题。
• 子树大小计算
  根植后，我们需要确定树节点子树的权重大小，如下所示。节点的子树大小可以描述为子树中的节点总数，子树仅由该节点组成，或者由该节点及其所有后代组成。
  这可以通过深度优先搜索 (DFS) 来完成。然后，我们通过递归过程传递每个节点子树的大小，从根节点开始。子树大小用于确定边的权重，因为边的权重定义了与节点相连的子树的相对大小。
• 将边分类为重边或轻边
  本质上，分解的前提基于边的分类。与每个节点相关联，我们研究其子节点并确定具有最大子树的子节点。节点与该子节点之间的出边被标记为重边。轻边是连接每个节点与其子树较小的子节点的边，所有其他边都被视为重边。
  这里的直觉是，从重边开始，尽可能地沿着重边走，直到到达需要切换重路径的点。这倾向于减少查询活动期间的路径切换次数。

如何将树分解为重路径？

一旦边被分类，我们就可以开始分解树为重路径的过程。重路径定义为以一个节点开始，仅遍历轻边直到无法形成更重的边。此时，我们停止一条重路径，并且在节点 a 的轻边下的任何子节点将被启动为一条新的重路径。

重路径被假定为尽可能连续。（前景高亮显示）；完成此分解后，树被简单地视为一组重路径，轻边被切断在两者之间。通过这种方式分解查询是可能的，因为这种方法可以通过段树或二进制索引树 (BIT) 等技术实现高效的解决方案。

用于查询的段树

之后，树被分解，然后利用段树或 BIT 等数据结构在重路径之上进行操作。这允许对重加权路径进行求和、最小值、最大值等探测。查询时会进行过渡以穿过轻边，以便跨越路径并仍然保持 O(log² n) 的高效时间。

重轻分解的应用

重轻分解适用于任何涉及树的问题，但对于需要高效处理路径查询和子树查询的问题尤其有用。

• 路径查询
  路径查询是 HLD 最重要的用途之一。例如，考虑一个优化问题，该问题定义为计算树中两个节点之间的和、最大值或最小值。那么 HLD 是最适合的。如果没有 HLD，此类查询将需要遍历整个树，并且至少需要 O(n) 的操作。但是，使用 HLD，查询可以分解为在不同重路径上的子查询，从而将时间复杂度降低到 O(log² n)。
• 动态树算法
  树的另一个重要应用是动态树问题，其中树的结构经常发生变化。尤其关注动态树（即随时间变化的树），使用 HLD 和高效的段树，可以动态地更新节点并进行查询。
• 竞赛编程
  HLD 因其轻松处理树问题的能力，也用于竞赛编程问题解决中。它经常用于涉及最近公共祖先 (LCA)、子树查询和基于路径的更新的问题。

编码

您可以在下面的 C++ 中找到 HLD 与段树的实现。该代码对树执行更新和路径查询。

输出

 
Sum of values between node 7 and 9: 24 
Sum of values between node 7 and 9 after update: 32    

说明

• 树的构建：在这种情况下，树的每个顶点都存储为邻接表中的一个项，同时指向连接到它所指向的顶点直接相连的其他相应顶点的链表。
• DFS 和分解：我们实现一个深度优先搜索算法来计算子树大小并区分重边和轻边。此外，树被划分为重路径。
• 段树：基于重路径，然后构建一个段树来支持快速的路径值更新和查询。
• 查询路径：query_path() 函数使用段树考虑两个节点之间的值之和。
• 更新：update() 函数用于设置节点的新值。

时间复杂度

重轻分解 (HLD) 的时间复杂度取决于两个关键操作：查询和更新。在这里，如果我们按照重路径和轻边划分树，执行这些操作会容易得多。

• 分解时间：DFS 用于了解子树大小以及段树中重边和轻边的位置。这是因为该过程涉及遍历树中的每个节点，这项任务可能非常耗时。
• 查询和更新时间：查询和更新在分解后都会通过多个重路径。由于路径可以对数地分割，每个查询或更新在任何重路径上需要 O(log n) 时间。考虑到任何两个节点之间存在 O(log n) 的重路径切换，查询或更新操作的时间复杂度为 O(log² n)。

因此，HLD 处理多个查询和更新时的时间复杂度为每个 O(log² n)。HLD 非常适合解决树上的路径问题，特别是当与段树或任何其他平衡良好的结构相结合时。

结论

总之，HLD 算法代表了一种已知的方法，该方法适用于包含路径查询和更新的特定树过程。它将树分割为重边和轻边的列表，以便于将树组织成用于查询的重路径结构。分解过程的第一步包括给树根并使用 DFS 计算子树的大小。这有助于将它们分类为重边（表示对最大子树的贡献）或轻边（其中重边形成反映树的大分支的路径）。

一旦树被分解为这些重路径，每条路径就被视为一个连续的段，这样就可以轻松使用段树或二进制索引树等数据结构来高效地回答路径查询。对于重路径，HLD 直接路由，而对于轻边，它切换到另一条路径，从而将问题分解为几个小问题来解决，并在过程中获得更好的结果。

HLD 的主要优点在于它能够回答路径查询（包括求和查询以及任意两个节点之间的最小或最大查询），并在对数时间内支持动态更新。这使得它在竞赛编程中特别有用，尤其是在频繁进行路径操作的树上。HLD 中查询和更新操作的成本为 O(log² n)，因为我们需要遍历多个重路径，然后执行高效的段树操作。