[Note] 树上差分

[L4] 树上差分

1. 生态位

• 识别:

  1. 批量路径修改: 给定 $M$ 条路径 $(u, v)$，对路径上的所有点（或边）增加权值 $w$。

  2. 最终单次查询: 修改完成后，查询每个点（或边）的最终权值。

  3. 离线处理: 不需要在线回答每次修改后的状态，而是先修改完再统计。

• 地位: 树论与降维技巧的结合。它是处理静态树上路径覆盖问题的 $O(N+M)$ 标配解法（优于树剖的 $O(M \log^2 N)$）。

• 用途: 解决路径计数、瓶颈边查找（如运输计划）、子树信息统计等问题。

2. 逻辑支点

2.1 核心原理：差分

树上差分是线性差分（b[l]+=v, b[r+1]-=v）在树上的推广。

其逆运算（前缀和）在树上表现为 “子树求和”。

2.2 两种模型

根据操作对象不同，分为 点差分 和 边差分。

A. 点差分

目标: 路径 $u \leftrightarrow v$ 上的所有 节点 权值 $+w$。

操作如下：

diff[u] += w;
diff[v] += w;
diff[Lca] -= w;
diff[fa[Lca]] -= w;

逻辑: $u$ 和 $v$ 的增量向上汇聚，在 $lca$ 处重叠为 $+2w$。

由于 $lca$ 本身需要 $+w$，所以减去一个 $w$。

而 $fa[lca]$ 不在路径上，需要把剩下的 $+w$ 也抵消掉。

B. 边差分

转化: 将边权下放给深度较深的节点（$u \to v$ 的边权存在 $v$ 上），转化为点权处理。

目标: 路径 $u \leftrightarrow v$ 上的所有 边 权值 $+w$。

操作如下:

diff[u] += w;
diff[v] += w;
diff[lca] -= 2 * w;

逻辑: $lca$ 代表的边（$lca \to fa[lca]$）不在路径上，所以必须在这里把 $u, v$ 上传上来的 $+2w$ 全部截断。

3. 实战部署

▶

树上差分

const int maxn = 3e5 + 50;
const int maxlg = 20;

vector< int > adj[maxn];
int up[maxn][maxlg], dep[maxn];
int diff[maxn], ans[maxn]; // diff: 差分数组, ans: 最终统计值
int n, m;

// 1. LCA 预处理
void dfs_lca( int u, int p )
{
    dep[u] = dep[p] + 1, up[u][0] = p;
    for( int i = 1; i < maxlg; ++ i ) up[u][i] = up[up[u][i - 1]][i - 1];
    for( int v : adj[u] ) if( v != p ) dfs_lca( v, u );
}

int get_lca( int u, int v )
{
    if( dep[u] < dep[v] ) swap( u, v );
    int dif = dep[u] - dep[v];
    for( int i = maxlg - 1; i >= 0; -- i ) if( ( diff >> i ) & 1 ) u = up[u][i];
    if( u == v ) return u;
    for( int i = maxlg - 1; i >= 0; -- i ) if( up[u][i] != up[v][i] ) u = up[u][i], v = up[v][i];
    return up[u][0];
}

// 2.1 修改：点差分
void modify_node( int u, int v, int w )
{
    int lca = get_lca( u, v );
    diff[u] += w;
    diff[v] += w;
    diff[lca] -= w;
    if( up[lca][0] != 0 ) diff[up[lca][0]] -= w; // 注意判根
}

// 2.2 修改：边差分
void modify_edge( int u, int v, int w )
{
    int lca = get_lca( u, v );
    diff[u] += w;
    diff[v] += w;
    diff[lca] -= 2 * w;
}

// 3. 统计：子树前缀和 (自底向上)
void dfs_sum( int u, int p )
{
    ans[u] = diff[u];
    for( int v : adj[u] )
    {
        if( v == p ) continue;
        dfs_sum( v, u );
        ans[u] += ans[v]; // 累加子树贡献
    }
}

4. 知识关联

• 基础依赖: LCA 体系 (所有的差分操作都依赖 LCA 定位)。

• 变体模型:

  • 桶差分: 当差分的对象不是权值 $+1$，而是某种属性（如时间 $t$）时，diff 数组变成一个 vector 或者全局桶。参考 P1600 天天爱跑步。

• 实战案例:

  • 点差分: P3258 松鼠的新家 (路径点权统计，注意起点终点去重)。

  • 边差分: [[220_Temporary/Change/P2680 运输计划]] (利用边差分快速求出被所有长路径覆盖的公共边)。