Next Topic

树上差分(tree difference)

数据结构与算法第四章树(tree) 树上差分(tree difference)

组别：提高级
难度：6

树上差分（Tree Difference）是一种在树形数据结构（例如二叉树、多叉树等）上进行差分操作的技术，主要用于树上查询和修改操作的高效实现。它的基本思想类似于数组上的差分数组，但在树结构中应用，需要结合树的特性来设计和实现。

以下是树上差分的一些主要应用和基本步骤：

主要应用

区间修改与查询：在树的某个子树中批量增加或减少某个值，然后查询某个节点或子树的累积结果。
路径修改与查询：在树的某条路径上批量增加或减少某个值，然后查询某个节点在路径上的累积结果。

树上差分的基本步骤：

初始化差分数组：
- 通常用一个与树的节点数相同的数组 diff 来记录差分信息。这个数组初始化为零。
标记节点：
- 对于一个查询或更新操作，如果要在某条路径上加上一个值 v，那么我们可以在路径的起点（比如节点 u）加上 v，在路径的终点（比如节点 v）的下一个节点减去 v，这样在处理完所有操作后，通过累加差分数组即可得到每个节点的真实值。
递归处理子节点：
- 从树的根节点开始，递归遍历树，将当前节点的差分值累加到其子节点上。这样子节点的值就等于它本身的差分值加上它父节点的累加值。
求解节点的最终值：
- 在遍历完树后，节点的最终值就是累加后的结果。这个过程可以用DFS或BFS完成。

代码实例:

/**************************************************************** 
 * Description: 树上差分的C++代码示例
 树的表示：用邻接表表示，tree[MAXN] 存储每个节点的子节点列表。
差分数组：diff[MAXN] 记录每个节点的差分值。
DFS遍历：dfs 函数从根节点开始遍历整棵树，通过累加父节点的值来计算每个节点的最终值。
路径更新：add 函数用于在从 u 到 v 的路径上加上 value。这里简单起见，假设 v 是 u 的直接子节点。
注意：
这里假设每个 v 都是 u 的直接子节点，因此差分直接在 v 处减去值。如果 v 不是 u 的子节点，需要更复杂的处理，比如找到 v 的下一个节点。
在实际应用中，v 的处理通常通过LCA（最近公共祖先）或其他算法来实现路径的准确差分。
 * Author: Alex Li
 * Date: 2024-08-13 12:16:36
 * LastEditTime: 2024-08-13 12:16:48
****************************************************************/
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005;

vector<int> tree[MAXN];
int diff[MAXN];  // 差分数组，用来记录增量
int result[MAXN]; // 最终结果

// DFS用于累加差分数组并计算最终结果
void dfs(int node, int parent) {
    // 累加当前节点的差分值到父节点的值上
    result[node] += diff[node];
    
    // 遍历所有子节点
    for (int child : tree[node]) {
        if (child != parent) {
            // 将父节点的值累加到子节点
            result[child] = result[node];
            dfs(child, node);
        }
    }
}

// 更新路径上的差分值
void add(int u, int v, int value) {
    diff[u] += value; // 在u上加上value
    diff[v] -= value; // 在v上减去value
}

int main() {
    int n, q;
    cin >> n >> q; // n是节点数，q是操作数

    // 输入树的边
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // 处理每个操作
    for (int i = 0; i < q; i++) {
        int u, v, value;
        cin >> u >> v >> value;
        add(u, v, value);
    }

    // 从根节点开始执行DFS，计算所有节点的最终值
    dfs(1, 0);

    // 输出每个节点的最终值
    for (int i = 1; i <= n; i++) {
        cout << "Node " << i << ": " << result[i] << endl;
    }

    return 0;
}

练习题：疫情控制 [NOIP2012 提高组] [P1084][5971]

2012_S_3

Previous Topic

Back to Lesson

Next Topic