树上差分

title: 树上差分
date: 2022-11-15 10:30:06
tags: 算法

本文章遵守知识共享协议 CC-BY-NC-SA ，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

树上点差分

问题描述：给定一个有n个点的树，所有节点的权值初始时都为0.有k次操作，每次指定两个点S,T,将S,T路径上的所有点权值+1，求操作完后所有点的值。

前置知识

• LCA （最好是倍增法）
• 差分

void treePointSequnenseAdd(int S,int T){
    diff[S]++;
    diff[T]++;
    int LCA = queryLCA(S,T);
    diff[LCA]--;
    diff[fa[LCA][0]]--;
}

树上边差分

概念：边权化点

边权化点：边权被转化成该点到父亲的连线。

diff[i]代表i到fa[i][0](父亲节点)的边权差分。

void treeLineSequnenseAdd(int S,int T){
    diff[S]++;
    diff[T]++;
    diff[LCA]-=2;
}