学习树上前缀和及树上差分前，一定要先会数组的前缀和与差分，要了解其思想，不会可以点击链接学习。

树上前缀和及树上差分需要使用到最近公共祖先（lca），可以参看我的另一篇文章：最近公共祖先(LCA)

自顶向下和自底向上两个概念用的地方不同，根据我的个人理解：一般树上前缀和用自顶向下，树上差分用自底向上。

树上前缀和

点权

为了方便，假设fa[i]表示节点i的父节点，w[i]表示节点i的点权(题目需要给出，或自己根据题目性质构造，总之在代码中一定是已知的)。

sum[i]为节点i到根节点路径上的节点的点权之和，即前缀和(一般sum[root]=0，但也可以不为0，先不管它)。

此时需要计算节点x和节点y的前缀和时，假设最近公共祖先为anc，假设路径为$x,x_1, x_2,\cdots, x_n, anc, y_1, y_2, \cdots, y_m, y$。则前缀和为$w[x]+w[x_1]+\cdots+w[x_n]+w[anc]+w[y_1]+\cdots+w[y_m]+w[y]$

其中sum[x]表示$w[x]+q[x_1]+\cdots+w[anc]+\cdots+w[root]$,sum[anc]表示$w[anc]+\cdots+w[root]$​，因此：

x到anc的前缀和为:sum[x]-sum[anc]（不包括anc的点权）

y到anc的前缀和为:sum[y]-sum[anc]（不包括anc的点权）

anc自己的点权为：sum[anc]-sum[fa[anc]]

于是最终的前缀和为：sum[x]+sum[y]-sum[anc]-sum[fa[anc]]

代码模版（并不完整）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int h[N], e[M], ne[M], idx; // 链式前向星存图（树）,已知
int sum[N], w[N] // sum为前缀和（待求），w为点的权值（已知）

void dfs(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        
        sum[j] = sum[u] + w[j];
        dfs(j, u);
    }
}

int main() {
    
    // 读图、存图、构造点权
    
    sum[root] = w[root] // 根节点单独初始化
    dfs(root, -1);
    
    // 求x到y的点权前缀和
    cout << sum[x] + sum[y] - sum[lca(x, y)] - sum[fa[lca(x, y)][0]]; // fa为lca实现代码中的数组，存储父节点。
}

边权

构造一个数组（sum），对于节点i，sum[i]表示节点i到根节点的边权之和，其中sum[root] = 0。

当需要求节点x和节点y的边权前缀和时，需要先求出两者的最近公共祖先，假设为anc。

则两者的前缀和为:sum[x] + sum[y] - 2*sum[anc]。这里可以自行画图理解一下。

两个节点之间的边权前缀和其实就是两个节点的树上距离。

代码模版（并不完整）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int h[N], w[M], e[M], ne[M], idx; // 链式前向星存图（树）,已知
int sum[N]; // 前缀和（待求）

void dfs(int u, int fa) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];

        if (j == fa) continue;
        sum[j] = sum[u] + w[i];
        dfs(j, u);
    }
}

int main() {
    // 读图、存图
    
    dfs(root, -1);
    
    // 求x到y的前缀和
	cout << sum[x] - sum[y] - 2 * sum[lca(x ,y)];
}

总结

根据树的特点（每个节点只有一个父节点），可以实现边权和点权的互相转化。即把节点x与父节点之间的边的边权作为节点x的点权。

可以发现，两者构造前缀和数组sum的代码一摸一样，只是求两节点间前缀和的代码略有不同：

  • 边权的树上前缀和(距离)：sum[x]+sum[y]-2*sum[anc]
  • 点权的树上前缀和：sum[x]+sum[y]-sum[anc]-sum[fa[anc]]

其实，因为要结合lca，dfs操作可以放在lca的预处理函数中一起预处理。（上面代码怕深搜爆栈，也可以用宽搜预处理）。

前面的内容其实是自顶向下实现的，因为树上前缀和单独使用时一般都是求树上距离的问题，只需要考虑自顶向下，而自底向上与自顶向下不同的地方在于，sum[i]的含义发生了改变。自底向上时，sum[i]表示节点i所在的子树的前缀和。即sum[root]的前缀和反而是最大的了。

一般自底向上求树上前缀和是需要和树上差分一起使用的，原因在于，树上差分是基于自底向上维护的。

树上差分

点权

点权的前缀和为：sum[x] + sum[y] - sum[lca(x, y)] - sum[fa[lca(x, y)]]

规定d[i]表示节点i与其父节点的点权之差。即d[i] = w[fa[i]] - w[i]

点权的差分(两点间的点权统一 加一)可以写为：

1
2
d[x]++, d[y]++; // 起点和终点加1
d[lca(x, y)]--, d[fa[lca(x, y)]]--; // 最近公共祖先及其父节点减一

下面啰嗦一下验证：

此时想要求节点x的点权：就是求包含节点x的子树的d[i]的自底向上的树上前缀和。

验证：可以发现d[x]++并不影响节点x的子树的d[i]，因此前缀和只比之前多1，表示只有节点x的点权加1了。同理，节点y也是一样。

而x到y到路径上的一个节点，假设是z(z是x的某个祖宗节点，但anc是z的祖宗节点)：它包含的子树中只有d[x]加一了，最终计算后的z的点权也是加一了，刚好加一。

再验证anc：计算其子树的d[i]前缀和之后，d[x]和d[y]都加一相当于加二，d[anc]减一，最终刚好也是加一。

再验证anc的父节点：计算其子树的d[i]前缀和之后，d[x]和d[y]都加一相当于加二，d[anc]和d[fa[anc]]都减一，相当于减二了，最终刚好就是不变。

计算节点u的点权代码模版：

1
2
3
4
5
6
7
8
9
10
11
12
13
int dfs(int u, int father) {
    int res = d[u];
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(j != father) {
            int s = dfs(j, u);
            res += s;
            ans = max(ans, res);
        }
    }

    return res;
}

边权

边权的前缀和：sum[x] + sum[y] - 2*sum[lca(x, y)]

规定d[i]表示节点i与其父节点的边权之差。即d[i] = w[fa[i]] - w[i]

边权的差分（两点间的边权都 加一）：

1
2
d[x]++, d[y]++; // 起点和终点加1
d[lca(x, y)] -= 2; // 最近公共祖先减2

同样，计算某个节点的边权，就是计算包含该节点的子树的d[i]的前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
int dfs(int u, int father) {
    int res = d[u];
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(j != father) {
            int s = dfs(j, u);
            res += s;
            ans = max(ans, res);
        }
    }

    return res;
}