树上前缀和与树上差分是处理树上路径查询与修改问题的重要算法技术。它们将线性结构上的“前缀和”与“差分”思想推广到了树状结构上，通常需要结合最近公共祖先（LCA）进行求解。

---

### 一、 树上前缀和

树上前缀和主要用于解决**静态树上路径属性查询**问题（如：求树上任意两点间路径的权值和），且不涉及修改操作。

根据权值所在位置的不同，分为**点权**和**边权**两种情况。设 $S\_u$ 表示从根节点到节点 $u$ 的路径权值和。

#### 1. 点权树上前缀和
已知各节点有权值 $val\_u$，要求查询节点 $u$ 到 $v$ 路径上所有节点的权值和。

*   **前缀和定义**： $S\_u = S\_{fa[u]} + val\_u$
    （其中 $fa[u]$ 表示 $u$ 的父节点，根节点的 $S\_{root} = val\_{root}$）
*   **路径查询公式**：
    对于任意两点 $u$ 和 $v$，设它们的最近公共祖先为 $LCA(u, v)$，则 $u$ 到 $v$ 路径上的点权和为：$Query(u, v) = S\_u + S\_v - S\_{LCA(u,v)} - S\_{fa[LCA(u,v)]}$
*   **原理**：
    $S\_u + S\_v$ 包含了从根到 $u$ 和从根到 $v$ 的路径。此时，从根到 $fa[LCA]$ 的路径被重复计算了两次，而 $LCA$ 节点自身也被重复计算了两次。为了只保留 $u \to v$ 路径上的点，需要减去一次 $LCA$ 及其祖先（即 $S\_{LCA}$），再减去一次 $LCA$ 的祖先（即 $S\_{fa[LCA]}$）。

#### 2. 边权树上前缀和
已知各边有权值，通常将边权下沉到子节点上（即节点 $u$ 记录它与父节点之间边的权值 $edge\_val\_u$），要求查询节点 $u$ 到 $v$ 路径上所有边的权值和。

*   **前缀和定义**：$S\_u = S\_{fa[u]} + edge\_val\_u$
    （根节点的 $S\_{root} = 0$）
*   **路径查询公式**：$Query(u, v) = S\_u + S\_v - 2 \times S\_{LCA(u,v)}$
*   **原理**：
    $S\_u + S\_v$ 重复计算了从根到 $LCA(u,v)$ 的路径边权两次。因为查询的是边权，而 $LCA$ 本身不代表 $u \to v$ 路径上的边，所以直接减去两倍的 $S\_{LCA}$ 即可。

---

### 二、 树上差分

树上差分主要用于解决**树上路径批量修改**问题。当需要对多条路径 $u \to v$ 进行整体加减操作，且最后只需一次性查询各节点或边的最终权值时，使用差分可以将每次修改的时间复杂度降低至 $O(1)$。

在所有修改完成后，通过一次自底向上的 DFS（即求子树差分值之和）来还原真实权值。同样分为**点差分**和**边差分**。

#### 1. 点树上差分
用于将路径 $u \to v$ 上所有**节点**的权值增加 $x$。

*   **差分操作**（设差分数组为 $D$）：
    $D\_u \gets D\_u + x$
    $D\_v \gets D\_v + x$
    $D\_{LCA(u,v)} \gets D\_{LCA(u,v)} - x$
    $D\_{fa[LCA(u,v)]} \gets D\_{fa[LCA(u,v)]} - x$
*   **权值还原**：
    修改完成后，执行一次后序遍历（DFS）。节点 $u$ 的最终权值 $val'\_u$ 为以 $u$ 为根的子树中所有节点的差分值之和：
    $val'\_u = \sum\_{w \in subtree(u)} D\_w$
*   **原理**：
    在 $u$ 和 $v$ 处分别加上 $x$，其影响会向上回溯。在 $LCA(u,v)$ 处减去 $x$，使得 $LCA$ 的祖先节点不再受到 $u$ 端向上传递的叠加影响；在 $fa[LCA(u,v)]$ 处再减去 $x$，使得其祖先节点也不再受到 $v$ 端向上传递的影响。最终只有 $u \to v$ 路径上的点权增加了 $x$。

#### 2. 边树上差分
用于将路径 $u \to v$ 上所有**边**的权值增加 $x$。边权同样下沉存储于子节点中。

*   **差分操作**：
    $D\_u \gets D\_u + x$
    $D\_v \gets D\_v + x$
    $D\_{LCA(u,v)} \gets D\_{LCA(u,v)} - 2x$
*   **权值还原**：
    与点差分一致，节点 $u$ 对应的边权最终值为其子树差分和：$edge\_val'\_u = \sum\_{w \in subtree(u)} D\_w$
*   **原理**：
    由于修改的是边，连接 $LCA(u,v)$ 及其父节点的边不属于 $u \to v$ 的路径。因此在 $LCA(u,v)$ 处直接减去 $2x$，可以同时消除 $u$ 和 $v$ 向上回溯对 $LCA$ 及其上方所有边产生的影响。

---

### 三、 总结与对比

| 技术维度 | 树上前缀和 | 树上差分 |
| :--- | :--- | :--- |
| **主要用途** | 解决静态路径查询（单次 $O(\log N)$ 或 $O(1)$ 配合 LCA） | 解决批量路径修改（单次修改 $O(1)$，最终还原 $O(N)$） |
| **操作方向** | 自顶向下（从根节点向子节点累计） | 自底向上（通过子树求和还原） |
| **关键辅助算法**| LCA（最近公共祖先） | LCA（最近公共祖先） |
| **点权修改公式** | 不需要修改（查询：$S\_u + S\_v - S\_{LCA} - S\_{fa[LCA]}$） | $D\_u += x$, $D\_v += x$, $D\_{LCA} -= x$, $D\_{fa[LCA]} -= x$ |
| **边权修改公式** | 不需要修改（查询：$S\_u + S\_v - 2 \times S\_{LCA}$） | $D\_u += x$, $D\_v += x$, $D\_{LCA} -= 2x$ |

**应用建议**：
*   当遇到需要多次询问树上两点路径和，且树结构及权值不发生变化时，优先考虑**树上前缀和**。
*   当遇到需要对多组路径进行权值加减，且仅在最后进行一次或少数几次全局查询时，**树上差分**是较为高效的离线处理方案。

一、树上前缀和

树上前缀和主要用于解决静态树上路径属性查询问题（如：求树上任意两点间路径的权值和），且不涉及修改操作。

根据权值所在位置的不同，分为点权和边权两种情况。设 $S_u$ 表示从根节点到节点 $u$ 的路径权值和。

1. 点权树上前缀和

已知各节点有权值 $val_u$，要求查询节点 $u$ 到 $v$ 路径上所有节点的权值和。

前缀和定义： $S_u = S_{fa[u]} + val_u$ （其中 $fa[u]$ 表示 $u$ 的父节点，根节点的 $S_{root} = val_{root}$）
路径查询公式：对于任意两点 $u$ 和 $v$，设它们的最近公共祖先为 $LCA(u, v)$，则 $u$ 到 $v$ 路径上的点权和为：$Query(u, v) = S_u + S_v - S_{LCA(u,v)} - S_{fa[LCA(u,v)]}$
原理： $S_u + S_v$ 包含了从根到 $u$ 和从根到 $v$ 的路径。此时，从根到 $fa[LCA]$ 的路径被重复计算了两次，而 $LCA$ 节点自身也被重复计算了两次。为了只保留 $u \to v$ 路径上的点，需要减去一次 $LCA$ 及其祖先（即 $S_{LCA}$），再减去一次 $LCA$ 的祖先（即 $S_{fa[LCA]}$）。

2. 边权树上前缀和

已知各边有权值，通常将边权下沉到子节点上（即节点 $u$ 记录它与父节点之间边的权值 $edge_val_u$），要求查询节点 $u$ 到 $v$ 路径上所有边的权值和。

前缀和定义：$S_u = S_{fa[u]} + edge_val_u$ （根节点的 $S_{root} = 0$）
路径查询公式：$Query(u, v) = S_u + S_v - 2 \times S_{LCA(u,v)}$
原理： $S_u + S_v$ 重复计算了从根到 $LCA(u,v)$ 的路径边权两次。因为查询的是边权，而 $LCA$ 本身不代表 $u \to v$ 路径上的边，所以直接减去两倍的 $S_{LCA}$ 即可。

二、树上差分

树上差分主要用于解决树上路径批量修改问题。当需要对多条路径 $u \to v$ 进行整体加减操作，且最后只需一次性查询各节点或边的最终权值时，使用差分可以将每次修改的时间复杂度降低至 $O(1)$。

在所有修改完成后，通过一次自底向上的 DFS（即求子树差分值之和）来还原真实权值。同样分为点差分和边差分。

1. 点树上差分

用于将路径 $u \to v$ 上所有节点的权值增加 $x$。

差分操作（设差分数组为 $D$）： $D_u \gets D_u + x$ $D_v \gets D_v + x$ $D_{LCA(u,v)} \gets D_{LCA(u,v)} - x$ $D_{fa[LCA(u,v)]} \gets D_{fa[LCA(u,v)]} - x$
权值还原：修改完成后，执行一次后序遍历（DFS）。节点 $u$ 的最终权值 $val'_u$ 为以 $u$ 为根的子树中所有节点的差分值之和： $val'_u = \sum_{w \in subtree(u)} D_w$
原理：在 $u$ 和 $v$ 处分别加上 $x$，其影响会向上回溯。在 $LCA(u,v)$ 处减去 $x$，使得 $LCA$ 的祖先节点不再受到 $u$ 端向上传递的叠加影响；在 $fa[LCA(u,v)]$ 处再减去 $x$，使得其祖先节点也不再受到 $v$ 端向上传递的影响。最终只有 $u \to v$ 路径上的点权增加了 $x$。

2. 边树上差分

用于将路径 $u \to v$ 上所有边的权值增加 $x$。边权同样下沉存储于子节点中。

差分操作： $D_u \gets D_u + x$ $D_v \gets D_v + x$ $D_{LCA(u,v)} \gets D_{LCA(u,v)} - 2x$
权值还原：与点差分一致，节点 $u$ 对应的边权最终值为其子树差分和：$edge_val'_u = \sum_{w \in subtree(u)} D_w$
原理：由于修改的是边，连接 $LCA(u,v)$ 及其父节点的边不属于 $u \to v$ 的路径。因此在 $LCA(u,v)$ 处直接减去 $2x$，可以同时消除 $u$ 和 $v$ 向上回溯对 $LCA$ 及其上方所有边产生的影响。

三、总结与对比

技术维度	树上前缀和	树上差分
主要用途	解决静态路径查询（单次 $O(\log N)$ 或 $O(1)$ 配合 LCA）	解决批量路径修改（单次修改 $O(1)$，最终还原 $O(N)$）
操作方向	自顶向下（从根节点向子节点累计）	自底向上（通过子树求和还原）
关键辅助算法	LCA（最近公共祖先）	LCA（最近公共祖先）
点权修改公式	不需要修改（查询：$S_u + S_v - S_{LCA} - S_{fa[LCA]}$）	$D_u += x$, $D_v += x$, $D_{LCA} -= x$, $D_{fa[LCA]} -= x$
边权修改公式	不需要修改（查询：$S_u + S_v - 2 \times S_{LCA}$）	$D_u += x$, $D_v += x$, $D_{LCA} -= 2x$

应用建议： * 当遇到需要多次询问树上两点路径和，且树结构及权值不发生变化时，优先考虑树上前缀和。 * 当遇到需要对多组路径进行权值加减，且仅在最后进行一次或少数几次全局查询时，树上差分是较为高效的离线处理方案。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

树上前缀和与差分

一、 树上前缀和