From 0302be796628f7c8b39f94b949e639dc8ed84d2c Mon Sep 17 00:00:00 2001 From: orzcyand1317 <36555123+orzcyand1317@users.noreply.github.com> Date: Wed, 6 Mar 2019 07:15:39 +0800 Subject: [PATCH] Update heavy-light-decomposition.md MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 修改了一些细节. 话说为什么「重边」会是「连接两个重儿子的边」啊...这么明显的东西没人发现嘛... --- docs/graph/heavy-light-decomposition.md | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/docs/graph/heavy-light-decomposition.md b/docs/graph/heavy-light-decomposition.md index 5bacf2d2..ae823126 100644 --- a/docs/graph/heavy-light-decomposition.md +++ b/docs/graph/heavy-light-decomposition.md @@ -4,13 +4,13 @@ 一棵静态(形状固定的)树,要求进行几种操作: -1. 修改 **单个节点/树上两点之间的路径/一个节点的子树上** 的所有点的值。 +1. 修改 **单个节点/树上两点之间的路径上/一个节点的子树中** 所有点的值。 -2. 查询 **单个节点/树上两点之间的路径/一个节点的子树上** 节点的值的 **和/极值/其他(具有较强的合并性)** 。 +2. 查询 **单个节点/树上两点之间的路径上/一个节点的子树中** 节点权值的 **和/极值/其他(具有较强的合并性)** 。 如果树的形态是一条链,那么我们只需要维护一个线段树,修改或查询线段树的值。 -因为这是一棵树,我们将这个树剖分成多个链,并用线段树修改或查询答案,这就是树链剖分的思想。 +因为这是一棵树,所以我们可以将这棵树剖分成多条链,并用数据结构来维护,这就是树链剖分的思想。 如果树是动态的,需要使用 **LCT** 来解决。 @@ -38,7 +38,7 @@ $son(x)$ 表示节点 $x$ 的 **重儿子** ,即所有儿子中子树大小最大的一个。 -定义 **重边** 表示连接两个重儿子的边。 +定义 **重边** 表示连接一个点及其重儿子的边。 定义 **重路径** 表示重边连成的一条链。 -- 2.11.0