【学习笔记】树上差分

分类

1.点差分

2.边差分

边差分

对差分和差分数组的理解一般都是停留再数组这种线性结构上，这可能会导致学习树上差分的时候无法理解这个概念。

树上差分一般应用于在树上的路径统计。

对于一棵树，可以设置差分数组表示经过边$i$（边$i$的定义是连接$i$到$i$父亲的这条边）的次数。

进行边差分是一般是从叶子节点向根节点进行差分。

若要在$(u,v)$的路径上进行加$i$，那我们要在差分数组进行下面操作。

d[u]+=i,d[v]+=i,d[lca(u,v)]-=2i;
//反之
d[u]-=i,d[v]-=i,d[lca(u,v)]+=2i;

任意两点之间有且只有一条简单路径。

如果是一棵无根树，那么确定根节点后，出根节点外每个点有且只有一个父节点。

点差分

对于图上的问题，有一些问题是带边权的，有一些问题则是带点权的。

对于这些问题，可以把两种权值相互转化，即边权转点权、点权转边权等操作。

但是其实有时候完全没有必要，点的差分数组比较好定义：

$d_i$表示$i$点一共被经过几次。那么对于路径$(u,v)$，就有以下的操作。

d[u]+=i,d[v]+=i,d[lca(u,v)]-=i,d[fa[lca(u,v)]]-=i;
//反之
d[u]-=i,d[v]-=i,d[lca(u,v)]+=i,d[fa[lca(u,v)]]+=i;